1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics Proof

  1. Jun 14, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that

    [tex]
    n5^n = \frac{5}{4} \sum_{k=0}^{n}k\begin{pmatrix}n\\k\end{pmatrix}4^k
    [/tex]

    (Hint: First Expand [tex](1+x^2)^n[/tex])

    3. The attempt at a solution

    So if I expand that I get

    [tex]
    (1+x^2)^n = (1+x^2)(1+x^2)...(1+x^2)
    [/tex] n times so it equals

    [tex]\sum_{k=0}^n (1+x^2)[/tex]

    Not sure where to go from there, unless I expanded that wrong?
     
  2. jcsd
  3. Jun 14, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is adding (1+x2) a bunch of times, not multiplying it. Try using the binomial theorem to get the correct expansion
     
  4. Jun 14, 2010 #3
    Hello! :smile:

    You need to use the binomial expansion formula for [tex](1+x^2)^n[/tex] for x=2.
     
  5. Jun 14, 2010 #4
    Ok, so I exapnded that using binomial expansion and evaluated it at x=2. I'll show my steps below

    [tex]
    (1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k
    [/tex]

    [tex]
    (1+4)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k
    [/tex]

    [tex]
    5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k
    [/tex]

    I believe that i then need to set [tex]5^n =4^k[/tex] and solve because the rest are constants I believe. I am drawing a major blank on that though...
     
  6. Jun 14, 2010 #5
    What are you talking about?
    Hint:
    Do something with:
    [tex]

    k\begin{pmatrix}n\\k\end{pmatrix}

    [/tex]
    like some algebraic stuff.
     
  7. Jun 14, 2010 #6
    What? The binomial Theorem states that

    [tex]
    (x+y)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}x^{n-k}y^k
    [/tex]

    so using that I got that

    [tex]
    (1+x^2)^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}(x^2)^k
    [/tex]

    Then evaluated that for x=2 to get

    [tex]
    5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix}4^k
    [/tex]

    From there there is no k times n choose k... So I am not really sure where that came from...
     
  8. Jun 14, 2010 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  9. Jun 14, 2010 #8
    So if I take d/dx I'll get

    [tex]
    n(1+x^2)^{n-1}(2x) = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k) (x^{2k-1})
    [/tex]

    which after putting 2 in for x I will then get

    [tex]
    4n5^{n-1} = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{2k-1})
    [/tex]

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

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

    but I am stuck from there.
     
  10. Jun 14, 2010 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    x^(2k-1) becomes 2^(2k-1) not 4^(2k-1). Clean that up.
     
  11. Jun 14, 2010 #10
    Ok I fixed that which then I realized that

    [tex]
    2^{2k-1} = 4^{k-1}
    [/tex]

    which I can then multiply both sides by [tex]4^{1}[/tex] to get

    [tex]
    16n5^n = \sum_{k=0}^{n} \begin{pmatrix}n\\k\end{pmatrix} (2k)(4^{k})5
    [/tex]

    Ok so I am short a 2 on the right hand side now...
     
    Last edited: Jun 14, 2010
  12. Jun 14, 2010 #11
    nevermind found my algebra mistake. thanks for the help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics Proof
  1. Combinatorics proof (Replies: 9)

Loading...