# Induction Proof with combination

1. Nov 7, 2013

### srfriggen

1. The problem statement, all variables and given/known data

Prove:

$\sum$$^{n}_{r=0}$2r($^{n}_{r}$) = 3n

2. Relevant equations

3. 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:

$\sum$$^{n+1}_{r=0}$2r($^{n}_{r}$) = 3n+1

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

32+2n+1($^{n+1}_{n}$)

Which I think equals: 32+2n+1($^{n}_{n-1}$)

Which equals: 32+2n+1*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.

2. Nov 7, 2013

### tiny-tim

hi srfriggen!

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

3. Nov 7, 2013

### srfriggen

So I can say, by the binomial theorem:

3n=(2+1)n=$\sum$$^{n}_{r}$($^{n}_{r}$)2r*1n-r

4. Nov 7, 2013

### tiny-tim

yup!

quicker?

Proof by induction, $(n!)^{2} \le (2n)!$. Mar 1, 2017