Combinatorics Proof: Prove n5^n = \frac{5}{4} Sum

[pupeye11]

Homework Statement

Prove that

<br /> n5^n = \frac{5}{4} \sum_{k=0}^{n}k\begin{pmatrix}n\\k\end{pmatrix}4^k<br />

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

The Attempt at a Solution

So if I expand that I get

<br /> (1+x^2)^n = (1+x^2)(1+x^2)...(1+x^2)<br /> n times so it equals

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

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

 

[Office_Shredder]

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

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

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

 

[njama]

Hello!

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

 

[pupeye11]

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

<br /> (1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k<br />

<br /> (1+4)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k<br />

<br /> 5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k<br />

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

 

[njama]

What are you talking about?
Hint:
Do something with:
<br /> <br /> k\begin{pmatrix}n\\k\end{pmatrix}<br /> <br />
like some algebraic stuff.

 

[pupeye11]

What? The binomial Theorem states that

<br /> (x+y)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}x^{n-k}y^k<br />

so using that I got that

<br /> (1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k<br />

Then evaluated that for x=2 to get

<br /> 5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k<br />

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

 

[Dick]

What? The binomial Theorem states that

<br /> (x+y)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}x^{n-k}y^k<br />

so using that I got that

<br /> (1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k<br />

Then evaluated that for x=2 to get

<br /> 5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k<br />

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

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.

 

[pupeye11]

So if I take d/dx I'll get

<br /> n(1+x^2)^{n-1}(2x) = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k) (x^{2k-1})<br />

which after putting 2 in for x I will then get

<br /> 4n5^{n-1} = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{2k-1})<br />

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

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

but I am stuck from there.

 

[Dick]

So if I take d/dx I'll get

<br /> n(1+x^2)^{n-1}(2x) = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k) (x^{2k-1})<br />

which after putting 2 in for x I will then get

<br /> 4n5^{n-1} = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{2k-1})<br />

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

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

but I am stuck from there.

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

 

[pupeye11]

Ok I fixed that which then I realized that

<br /> 2^{2k-1} = 4^{k-1}<br />

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

<br /> 16n5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{k})5<br />

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

 

[pupeye11]

nevermind found my algebra mistake. thanks for the help.