1. Limited time only! Sign up for a free 30min personal 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!

Proof by induction

  1. Oct 14, 2013 #1
    I am having issues with my homework questions, I can get them all the way to the very alst step but i seem to consistently get stuck trying to connect them to the answer at the end. (this will make more sense when you see the problem) I'm going to post both proofs I've worked on so far one after the other.

    [STRIKE]Problem 1
    1. The problem statement, all variables and given/known data
    Prove by induction: For all n that are an element of the natural numbers, Ʃ (i=1, n) 4i = (4n+1-4)/3


    2. Relevant equations


    3. The attempt at a solution

    Proof :
    1. For n=1, the LHS(left hand side)= 41 while the RHS(right hand side)= (41+1-4)/3 = 12/3 = 4
    This TCIT for n=1

    2. Assume TCIT for n=k, so Ʃ(i=1, k) 4i = (4k+1-4)/3
    for n=k+1, LHS is Ʃ(i=1, k) 4i = (41+42+...+4k)+(4k+1)

    = Ʃ(i=1, k) 4i + 4k+1
    = (4k+1-4)/3 + 4k+1 by assumption
    and this is where I get stuck, I know i need to get it to work out to be (4(k+1)+1-4)/3 but I don't see how
    [/STRIKE]

    Problem 2
    1. The problem statement, all variables and given/known data
    Prove by induction: For all n that are an element of the natural numbers, 1*1!+2*2!+...+n*n! = (n+1)!-1

    3. The attempt at a solution
    Proof:
    1. for n=1, LHS=1*1! = 1 while RHS = (1+1)! -1 = 1
    thus TCIT for n=1
    2. Assume TCIT for n=k, so 1*1!+2*2!+...+k*k! = (k+1)! -1
    for n=k+1 the LHS = (1*1!+2*2!+...+k*k!)+(k+1)(k+1)!
    =(k+1)!-1 + (k+1)(K+1)! by assumption
    and again I can't figure out how to get it to come out to ((k+1)+1)!-1
     
    Last edited: Oct 14, 2013
  2. jcsd
  3. Oct 14, 2013 #2
    I figured 1 out, I was just not thinking about the law of exponents, once I realized 4k+1 = 4*4k it all worked itself out in my head. I'm still lost on the 2nd one though
     
  4. Oct 14, 2013 #3

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    $$\forall n \in \mathbb{N}, \sum_{1}^n 4^i = \frac{4^{n+1}-4}{3}$$

    $$\sum_{1}^{k+1} 4^i = 4^{k+1}+\sum_{1}^k =4^{k+1} + \frac{4^{k}-4}{3}$$

    That about right?
    The trick here is to separate out the fractions and realize that ##4^k = \frac{1}{4}4^{k+1}##
    [edit] Oh you got it.
     
  5. Oct 14, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Take the difference between the k+1 case and the k case. So you want to prove (k+1)(k+1)!=(k+2)!-(k+1)!. That really isn't too hard, is it?
     
  6. Oct 14, 2013 #5

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    $$\forall n \in \mathbb{N}, \sum_{i=1}^n i( i!) = (n+1)!-1$$

    That works:
    $$\sum_{i=1}^{k+1} i( i!) = (k+1)(k+1)! + \sum_{i=1}^k i( i!) = (k+1)(k+1)! +[(k+1)!-1]$$

    Hint: rewrite with u(k)=(k+1)! and stand back.
     
    Last edited: Oct 15, 2013
  7. Oct 14, 2013 #6
    I'm missing something here, how did you simplify to k(k+1)! ? and I don't understand what you mean by u(k) could you clarify a little for me? I must be missing some important law about factorials that is making this so confusing.
     
  8. Oct 15, 2013 #7

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I mean every time you see a (k+1)!, put a u... but that may not make it jump out as much to you...
    I made a typo though ... edited (thanks)

    You are trying to show:
    $$\text{LHS}= (k+1)(k+1)! +[(k+1)!-1]=(k+2)!-1=\text{RHS}$$ ... another approach is to put (k+2)! in terms of (k+1)! ... i.e. expand out the factorial in the RHS and look at it.
    OR: put (k+1)(k+1)! inside a single factorial.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...