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.