# Combinatorics Proof

1. Jun 14, 2010

### pupeye11

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

Prove that

$$n5^n = \frac{5}{4} \sum_{k=0}^{n}k\begin{pmatrix}n\\k\end{pmatrix}4^k$$

(Hint: First Expand $$(1+x^2)^n$$)

3. The attempt at a solution

So if I expand that I get

$$(1+x^2)^n = (1+x^2)(1+x^2)...(1+x^2)$$ n times so it equals

$$\sum_{k=0}^n (1+x^2)$$

Not sure where to go from there, unless I expanded that wrong?

2. Jun 14, 2010

### Office_Shredder

Staff Emeritus
This is adding (1+x2) a bunch of times, not multiplying it. Try using the binomial theorem to get the correct expansion

3. Jun 14, 2010

### njama

Hello!

You need to use the binomial expansion formula for $$(1+x^2)^n$$ for x=2.

4. Jun 14, 2010

### pupeye11

Ok, so I exapnded that using binomial expansion and evaluated it at x=2. I'll show my steps below

$$(1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k$$

$$(1+4)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k$$

$$5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k$$

I believe that i then need to set $$5^n =4^k$$ and solve because the rest are constants I believe. I am drawing a major blank on that though...

5. Jun 14, 2010

### njama

Hint:
Do something with:
$$k\begin{pmatrix}n\\k\end{pmatrix}$$
like some algebraic stuff.

6. Jun 14, 2010

### pupeye11

What? The binomial Theorem states that

$$(x+y)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}x^{n-k}y^k$$

so using that I got that

$$(1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k$$

Then evaluated that for x=2 to get

$$5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k$$

From there there is no k times n choose k... So I am not really sure where that came from...

7. Jun 14, 2010

### Dick

That's fine. But it's not the expression you want to prove. Try taking d/dx of both sides before you put x=2.

8. Jun 14, 2010

### pupeye11

So if I take d/dx I'll get

$$n(1+x^2)^{n-1}(2x) = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k) (x^{2k-1})$$

which after putting 2 in for x I will then get

$$4n5^{n-1} = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{2k-1})$$

Then from there I figured I could multiply both sides by 5^1 to get

$$4n5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{2k-1})(5)$$

but I am stuck from there.

9. Jun 14, 2010

### Dick

x^(2k-1) becomes 2^(2k-1) not 4^(2k-1). Clean that up.

10. Jun 14, 2010

### pupeye11

Ok I fixed that which then I realized that

$$2^{2k-1} = 4^{k-1}$$

which I can then multiply both sides by $$4^{1}$$ to get

$$16n5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{k})5$$

Ok so I am short a 2 on the right hand side now...

Last edited: Jun 14, 2010
11. Jun 14, 2010

### pupeye11

nevermind found my algebra mistake. thanks for the help.