# Binomial Expansion

• May 3rd 2011, 04:55 AM
mathguy80
Binomial Expansion
Hi Guys,

Need a little help with this one, Not sure how to proceed.

Two positive integers, $a,b$ are connected by the relation $a = b - 1$. By using a binomial expansion show that for all positive integral values of n the expression $a^{2n} + 2nb - 1$ is exactly divisible by $b^2$. By choosing suitable values of a and n, show that $2^{40} + 119$ is divisible by 9, and hence that $2^{39} + 1$ is divisible by 9.

I tried putting the substitution for $a$ into the equation, and did a binomial expansion of $(b - 1)^{2n}$, but not sure where that is supposed to lead. It seems like another longer equation.

• May 3rd 2011, 06:02 AM
mr fantastic
Quote:

Originally Posted by mathguy80
Hi Guys,

Need a little help with this one, Not sure how to proceed.

Two positive integers, $a,b$ are connected by the relation $a = b - 1$. By using a binomial expansion show that for all positive integral values of n the expression $a^{2n} + 2nb - 1$ is exactly divisible by $b^2$. By choosing suitable values of a and n, show that $2^{40} + 119$ is divisible by 9, and hence that $2^{39} + 1$ is divisible by 9.

I tried putting the substitution for $a$ into the equation, and did a binomial expansion of $(b - 1)^{2n}$, but not sure where that is supposed to lead. It seems like another longer equation.

I suggest you write out the first few terms and the last few terms of $(b - 1)^{2n}$. Then add 2nb and subtract 1. You can't help but notice something ....
• May 3rd 2011, 06:06 AM
Moo
Hello,

Some steps have been volutarily skipped.

let's expand http://latex.codecogs.com/png.latex?(b-1)^{2n}

http://latex.codecogs.com/png.latex?...2n}^k%20(-b)^k

Considering it mod b², we can remove the powers of b superior to 2, because if for example http://latex.codecogs.com/png.latex?k\geq 2, b^2 can be factored out and since b^2=0 mod b^2, it cancels all the terms with k>2.

Hence http://latex.codecogs.com/png.latex?...(-b) \bmod b^2

• May 3rd 2011, 06:16 AM
melese
The Binomial Theorem gives $(b-1)^{2n}=1-\binom{2n}{1}b+\binom{2n}{2}b^2+\cdots$. Note that $\binom{2n}{1}=2n$ and that all terms after the second are divisible by $b^2$. Thus, $(b-1)^{2n}=1-2nb+Ab^2$, where $A$ is some integer.

Therefore, $a^2+2nb-1=Ab^2$.

This is essentially the same idea as in Moo's post.
• May 3rd 2011, 08:14 AM
mathguy80
Thanks guys. @Moo, sorry to sound stupid. I got the summation part, but the rest of the notation went way over my head. :(

@melese. Got it! The 1 and 2nb terms cancel out, rest all terms have powers of b >= 2. Then rest a=2,b=3 and n=20, forms similar expression hence divisible, which checks out. Thanks!
• May 3rd 2011, 09:40 AM
Moo
What part exactly ? C_{2n^k} corresponds to http://latex.codecogs.com/png.latex?\binom{2n}{k}
And the sum goes to 1 because after 2 it has no interest (=0)
• May 3rd 2011, 08:18 PM
mathguy80
Yup, I was confused by the C_ notation. So that corresponds to n choose k. That clears things up, thanks!