use induction to show sum [k=0,n] (C(n,k) 2^k) = 3^n

[green_tea]

Hi! I need some help with this:

I have to show, with mathematic induction, that:

n
? ( C(n, k) * 2^k) = 3^n
k=0

is true for all real n.


with C(n, k) i mean
(n) = n! / (k!(n-k)! (the parantesis' to the left should be covering both the n and the k under it)
k

So, I've come this far: I showed that the formula is true for n=0 and now I have to show that it's true for n+1. And I'm stuck. I've been thinking for days and I just can't figure it out. I tried many different things, like splitting the summation in two so that I have

n
? ( C(n+1,k) * 2^k) + C(n+1,n+1)*2^(n+1) =
k=0

n
? ( C(n+1,k) * 2^k) + 2^(n+1)
k=0

I also tried to use the binomial coefficients but I couldn't...

I just can't figure out what to do next and now I'm in desperate need for some help. If anyone could just tell me how I should start solving this one, I would be sooooooo greatefull!!!
Please, help me somebody!!!!!!!!!!!!!!!

 

[pka]

Re: I need HELP with induction!!!!!!

Induction is the absolute worst way to prove this property.
To do the induction step, moving from N to N+1 you need to know the following:
\(\displaystyle {{N+1} \choose {k}} = {{N} \choose {k}} + {{N} \choose {k-1}}\)
Then some very very careful manipulation of the Sum will give you the result.
But those manipulations are very difficult to get right.

Here is the easy way to prove this.
\(\displaystyle \left( {x + y} \right)^N = \sum\limits_{k = 0}^N {{{N} \choose {k}}x^{N - k} y^k }\).
Let \(\displaystyle x=1 \;\&\;y=2\).

 

[green_tea]

Re: I need HELP with induction!!!!!!

Thanx for responding so fast! Yeah I kind of figured that it's hard to prove it with induction. But the other way is good. I actually figuerd it out as well, after posting my question here So my problem is solved. Thanks once again

 

[Pklarreich]

Re: I need HELP with induction!!!!!!

Thanx for responding so fast! Yeah I kind of figured that it's hard to prove it with induction. But the other way is good. I actually figuerd it out as well, after posting my question here So my problem is solved. Thanks once again

Well, I don't know about that. If you were told to use M.I. then you have to use M.I. [Remember the Clint Eastwood rule: Man's gotta do what a man's gotta do.] So you have to work out the algebra. It goes like this: (yes, it IS messy.)

Hypothesis: sum [ C(n, k) * 2^k ] = 3^n

Now evaluate:

n+1
sum [ C(n+1, k) * 2^k ]
k=0


= C(n+1,0) + C(n+1,1) 2 + C(n+1,2) 2^2 + ... + C(n+1,n) 2^n + 2^n+1 =

1 + (C(n,1)+C(n,0)) 2 + (C(n,2)+C(n,1)) 2^2 + ... + (C(n,n) + C(n,n-1) 2^n + 2^n+1

That includes:

2( C(n,0) + C(n,1) 2 + C(n,n-1)2^n-1 + C(n,n)2^n), which by hypothesis, gives

2 * 3^n + 1 + (C(n,1)) 2 + (C(n,2)) 2^2 + ... + (C(n,n)) 2^n =

2 * 3^n + (C(n,0) + (C(n,1)) 2 + (C(n,2)) 2^2 + ... + (C(n,n)) 2^n

which gives another 3^n

2 * 3^n + 3^n = 3^n(2 + 1) = 3^n+1