Results 1 to 2 of 2

Math Help - Proof a recursive formula with induction

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    2

    Proof a recursive formula with induction

    Hi all!


    I'm new here and I could use some help on a homework question.

    Problem
    Given the following recursive definition:

    \\ $a_0=1$ \\ $a_1=2$ \\ $a_n=\frac{(a_{n-1})^2}{a_{n-2}}$

    I have to proof, using induction, that

    \\ $a_n=2^n


    My current proof is as follows:

    Proof
    Base step
    The formula is correct for the cases n=0 and n=1 (Can be easily verified).

    Induction step
    Assume the formula is correct for n, we can fill this in:

    $a_n = \frac{(2^{n-1})^2}{2^{n-2}}$

    $a_n = \frac{2^{2n-2}}{2^{n-2}}$

    $a_n = \frac{2^{n-2} \times 2^n}{2^{n-2}}$

    $a_n = 2^n$


    However, I think I am missing some important induction steps. I don't see the connection between the base step and the induction step.

    Any help is appreciated, thanks in advance!
    Last edited by CaptainBlack; September 27th 2011 at 08:50 PM.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Proof a recursive formula with induction

    In the induction step, you should fix an arbitrary n >= 2 and assume that the claim holds for n - 1 and n - 2. Then you need to prove it for n. In other words, you prove the following statement where P(n) denotes the claim for n: "For all n >= 2, if P(n - 2) and P(n - 1), then P(n)." Since you proved P(0) and P(1), the induction step gives P(2), then from P(1) and P(2) you get P(3) and so on.

    The calculations you did are correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive Formula
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 13th 2010, 09:59 PM
  2. recursive formula
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 9th 2010, 09:36 PM
  3. recursive formula
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 27th 2009, 01:13 PM
  4. [SOLVED] Recursive sequence induction proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 21st 2008, 11:04 PM
  5. Recursive induction
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 11th 2007, 11:34 AM

/mathhelpforum @mathhelpforum