Induction Proof with combination

[srfriggen]

Homework Statement

Prove:

[itex]\sum[/itex][itex]^{n}_{r=0}[/itex]2^r([itex]^{n}_{r}[/itex]) = 3ⁿ

Homework Equations

The Attempt at a Solution

I proceeded by induction:

Testing the base case for n=0 is correct.


Moving right along to try to show:

[itex]\sum[/itex][itex]^{n+1}_{r=0}[/itex]2^r([itex]^{n}_{r}[/itex]) = 3ⁿ⁺¹



This is where I'm getting stuck. I can obtain:

3²+2ⁿ⁺¹([itex]^{n+1}_{n}[/itex])

Which I think equals: 3²+2ⁿ⁺¹([itex]^{n}_{n-1}[/itex])

Which equals: 3²+2ⁿ⁺¹*n




I am not sure how to proceed after this. Any help would be greatly appreciated.

also, this was a problem on a test I took yesterday.

 

[tiny-tim]

hi srfriggen!

much easier would be a proof using the binomial expansion ((a + b)ⁿ)

 

[srfriggen]

So I can say, by the binomial theorem:

3ⁿ=(2+1)ⁿ=[itex]\sum[/itex][itex]^{n}_{r}[/itex]([itex]^{n}_{r}[/itex])2^r*1^n-r

 

[tiny-tim]

yup!

quicker? ​