Another math problem.

[Novriil]

Spoiler

4^n + 15n - 1 = 9k
4^(n+1) + 60 n - 4 = 4*9k
4^(n+1) + 15n -1 + 45n - 3 = 4*9k
4^(n+1) + 15(n+1) -1 + 45n - 18 = 4*9k
4^(n+1) + 15(n+1) -1 = 4*9k + 18 - 45n = 9*(4k + 2 - 5n)

can somebody explain since the bold part. This ise the first line I can't understand how he got it.

 

[uberCuber]

can somebody explain since the bold part. This ise the first line I can't understand how he got it.

4^(n+1) + 15n -1 + 45n - 3 = 4*9k
4^(n+1) + 15(n+1) -1 + 45n - 18 = 4*9k

since the 4^(n+1) and the -1 + 45n are the same in both lines, take them out to make it clearer:

15n - 3
15(n+1) - 18

he added another 15 to the 15n, making it (n+1) * 15 instead of just n * 15, and then to keep it equal, subtracted 15 at the end, changing the - 3 into a - 18.

 

[keemy]

slightly different inductive proof(well basically the same but a little shorter)

clearly true for \( n=0, 0+1+8=9 \)

assuming true up to n let \( n^3\equiv k \pmod 9, (n+1)^3 + (n+2)^3 \equiv l \pmod 9, k+l\equiv 0 \pmod 9 \)
so just nts \( n^3\equiv (n+3)^3 \pmod 9 \)
which is true since \( 9n^2+27n+27\equiv 0 \pmod 9 \)
so \( n^3 +(n+1)^3 + (n+2)^3 \equiv (n+1)^3 + (n+2)^3 + (n+3)^3 \equiv 0 \pmod 9 \)

 

[cmhardw]

slightly different inductive proof(well basically the same but a little shorter)

clearly true for \( n=0, 0+1+8=9 \)

assuming true up to n let \( n^3\equiv k \pmod 9, (n+1)^3 + (n+2)^3 \equiv l \pmod 9, k+l\equiv 0 \pmod 9 \)
so just nts \( n^3\equiv (n+3)^3 \pmod 9 \)
which is true since \( 9n^2+27n+27\equiv 0 \pmod 9 \)
so \( n^3 +(n+1)^3 + (n+2)^3 \equiv (n+1)^3 + (n+2)^3 + (n+3)^3 \equiv 0 \pmod 9 \)

that's pretty

 

[maggot]

oooh, very nice. deep @_@ i wonder if he put this on his homework, however, the teacher would know he got help LMAO! this is very nice though.
the line i really like in this is that
it is clearly true for n=0, 0+1+8=9 . . .
i find this line to bring it together where sometimes 0 can be ambiguous. hence sometimes the need for proof of 0 exclusively to include 0 from the set of naturals. good job!

 

[malcolm]

\( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} = 2C^{n+1}_{3} + n \) which is obviously an integer. Actually any polynomial in \( x \) which takes integer values for integer values of \( x \) can be written as a sum of binomial coefficients in \( x \), you can prove this by induction on the degree

 

[keemy]

\( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} = 2C^{n+1}_{3} + n \) which is obviously an integer. Actually any polynomial in \( x \) which takes integer values for \( x \) can be written as a sum of binomial coefficients in \( x \), you can prove this by induction on the degree

(fixed mistake I think)

hmm I'm not sure how the later statement helps with the first(I mean unless there is a trick for finding sum of of binomial coefs). But either way that's pretty nice, I always like proofs that an expression must be an integer by showing it counts something.

 

[malcolm]

Thanks, I've fixed the mistake. The first statement doesn't follow from the second, but the second does tell us that if the sum of three consecutive cubes is always divisible by 9, then we must be able to write \( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} \) as a sum of binomial coefficients, since the polynomial \( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} \) takes integer values whenever n is an integer. The second statement is just an interesting fact - try to prove it!

 

[keemy]

I think I got a proof (to malcolm's statement)

lemma 1: given 2 polynomials \( P(x) \) and \( Q(x) \) with said properties \( P(x)\pm+Q(x) \) also has said properties.(duh)

lemma 2: if \( P(x) \) has said properties and \( deg(P(x))=l \) then the denominator of the coefficient of the \( x^l \) term is at most \( l! \)(and divides \( l! \)). This is slightly less obvious but if you notice that \( (x+1)(x+2)\ldots(x+l) \) is always divisible by \( l! \) and that there isn't any other polynomial that will have more factors or be divisible by more than \( l \) @ all \( x \) it becomes clearer.

so now a proof by induction

again the base is easy: if \( P(x) \) has said properties and \( deg(P(x))=0 \) then \( P(x)= A\tbinom k0 \) for some \( A\in\mathbb{Z} \)

now given that any polynomial \( P(x) \) with said properties and degree \( deg(P(x))=l \) can be written as the sum of some binomial coefficients.

well lets work backwards and assume we have a \( Q(x) \) with \( deg(Q(x))=l+1 \) and said properties now we know by lemma 2 that the denominator of the coefficient(lets call this \( a_{l+1} \)) of the \( x^{l+1} \) term is at most \( (l+1)! \)

then lets take just take the binomial coefficient \( {x+l+1 \choose l+1} = \frac{(x+1)(x+2)\ldots(x+l+1)}{(l+1)!} \), set\( m=\frac{(l+1)!}{a_{l+1}} \)and make the polynomial \( R(x)=m{x+l+1 \choose l+1} \) noting that the coefficient of the \( x^{l+1} \) term is equal to \( a_{l+1} \)

now just have \( Q(x)-R(x)=P(x) \) (by lemma 1 they all have said properties) and notice \( deg(P(x))=l \)

so any \( Q(x) \) with said properties and degree \( l+1 \) can be written as \( P(x) + R(x)= Q(x) \) for some \( P(x) \) with said properties and degree \( l \) and some \( R(x)= B{x+l+1 \choose l+1} \) with \( B \in \mathbb{Z} \)