Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Plato

Math Help - Mathematical Induction question

  1. #1
    Newbie
    Joined
    Feb 2013
    From
    kuala lumpur
    Posts
    6

    Mathematical Induction question

    Question:Prove by mathematical induction that if Un+2= 3Un+1 - 2Un for all positive integers n, and U1 = 1 , U2 = 3 , then Un = 2n - 1.

    How to deal with relations that includes 3 terms in mathematical induction?
    This is how far I got:

    Un = 2n - 1
    let n=1,
    LHS: U1=1

    RHS: 2-1=1
    RHS=LHS

    Assume when n=k, the equation is true: Uk = 2k -1
    Proof that Uk+1=2k+1-1

    UK+1= 3Uk -2Uk-1
    =3( 2k - 1) -2Uk-1 Then I couldn't proceed with the k-1 there. Can anyone help?

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,707
    Thanks
    1637
    Awards
    1

    Re: Mathematical Induction question

    Quote Originally Posted by tsyet12 View Post
    Question:Prove by mathematical induction that if Un+2= 3Un+1 - 2Un for all positive integers n, and U1 = 1 , U2 = 3 , then Un = 2n - 1.

    How to deal with relations that includes 3 terms in mathematical induction?
    This is how far I got:

    Un = 2n - 1
    let n=1,
    LHS: U1=1

    RHS: 2-1=1
    RHS=LHS

    Assume when n=k, the equation is true: Uk = 2k -1
    Proof that Uk+1=2k+1-1

    UK+1= 3Uk -2Uk-1
    =3( 2k - 1) -2Uk-1 Then I couldn't proceed with the k-1 there. Can anyone help?
    Suppose that this true for each 1\le J\le K.

    Look at
    \begin{align*} U_{K+1} &= 3U_k-2U_{K-1}\text{ by definition}\\  &= 3[2^K-1]-2[2^{K-1}-1] \\ &=3\cdot 2^K-3-2^K+2 \\ &=2^{K+1}-1\end{align*}.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2013
    From
    kuala lumpur
    Posts
    6

    Re: Mathematical Induction question

    How can u use substitution Uk-1 = 2k-1 - 1 ?
    The thing we are going to proof by induction is Un=2n-1 . A number is substitute to check if any number fulfills the equation. And if yes, we assume that there are a set of numbers that fulfills the equation and let it be k. Hence , Uk=2k -1 is deduced and usable in further calculations. Then we proceed to proving that "k+1" or "k-1" also fulfills the equation, and if yes, the equation is correct, proven by induction.

    But, in the process of proving Uk+1, you substitute Uk-1 (which wasn't deduced or proven). Is that valid? And, isn't that assuming that the equation is already correct?

    If you assume that Uk=2k-1 and Uk-1=2k-1 -1 at the same time, isn't that already assuming the equation correct?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,707
    Thanks
    1637
    Awards
    1

    Re: Mathematical Induction question

    Quote Originally Posted by tsyet12 View Post
    How can u use substitution Uk-1 = 2k-1 - 1 ?
    The thing we are going to proof by induction is Un=2n-1 . A number is substitute to check if any number fulfills the equation. And if yes, we assume that there are a set of numbers that fulfills the equation and let it be k. Hence , Uk=2k -1 is deduced and usable in further calculations. Then we proceed to proving that "k+1" or "k-1" also fulfills the equation, and if yes, the equation is correct, proven by induction.

    But, in the process of proving Uk+1, you substitute Uk-1 (which wasn't deduced or proven). Is that valid? And, isn't that assuming that the equation is already correct?

    If you assume that Uk=2k-1 and Uk-1=2k-1 -1 at the same time, isn't that already assuming the equation correct?
    Surely you know about strong induction?
    That was the point of saying it holds for 1\le J\le K.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Mathematical Induction question

    Given some property of numbers P, regular induction proves P(1), on the basis of P(1) it proves P(2), on the basis of P(2) it proves P(3), and in general it uses P(k) to prove P(k + 1). Eventually you can prove P(n) for every n, so you may consider "for all n, P(n)" proved.

    Strong induction also proves P(1), and on the basis of P(1) it proves P(2). Then it uses both P(1) and P(2) to prove P(3), it uses P(1), P(2) and P(3) to prove P(4), and in general it uses all of P(1), ..., P(k) to prove P(k + 1). In particular, when proving P(k + 1) you may use not only P(k), but P(k - 1) (as long as k > 1). Eventually you again can prove P(n) for every n. Note that strong induction makes the induction step easier because you have more assumptions to prove P(k + 1).

    It is important that if you started with P(1), then in proving P(k + 1) you may use P(k - 1) only when k > 1 (otherwise, P(k - 1) becomes P(0), which you have not proved). How then do we prove P(k + 1) for k = 1, i.e., P(2)? It has to be proved separately, not as a part of the induction step. Thus, strong induction may have more than one base case. But even base cases can be considered as induction steps if the rule is to prove P(k) from all P(j) where 1 ≤ j < k. In particular, P(1) is proved without assumptions since there is no j such that 1 ≤ j < 1.

    See also Wikipedia.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2013
    From
    kuala lumpur
    Posts
    6

    Re: Mathematical Induction question

    Ok, thanks, you guys.I understand now! Appreciate it very much ^^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help with Mathematical induction question?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 29th 2012, 10:20 PM
  2. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 4th 2011, 06:30 PM
  3. Mathematical Induction question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 26th 2009, 08:05 PM
  4. Need help on Mathematical Induction question
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 27th 2008, 10:32 AM
  5. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 24th 2008, 05:11 AM

Search Tags


/mathhelpforum @mathhelpforum