Results 1 to 3 of 3

Math Help - Easy proof by induction

  1. #1
    Newbie
    Joined
    Oct 2006
    Posts
    6

    Easy proof by induction

    Hey everyone, I'm new here. I've taken a few classes which dealt with proofs by induction, and recently a friend came to me for help with one. I'm so rusty now though, but I know it should not be hard. The problem is to show that the solution to x-sub-n+1 = r (x-sub-n) is x-sub-n = r^n(x-sub-zero). Can anyone help solve this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by theclasher View Post
    Hey everyone, I'm new here. I've taken a few classes which dealt with proofs by induction, and recently a friend came to me for help with one. I'm so rusty now though, but I know it should not be hard. The problem is to show that the solution to x-sub-n+1 = r (x-sub-n) is x-sub-n = r^n(x-sub-zero). Can anyone help solve this?
    Let me make sure I've got this right. You need to solve
    x_{n + 1} = r \cdot x_n

    and verify it has the solution
    x_n = r^n \cdot x_0

    There are two ways you can do this:
    1) Start with the solution and verify it fits the equation. (Work backwards, in other words.)

    2) Start with the equation for x_n and work your way down, step by step.

    The first method is practically trivial and probably not what you want so I'll work the second one.

    x_n = r \cdot x_{n - 1}

    So
    x_{n - 1} = r \cdot x_{n - 2}

    Putting this into your first expression gives:
    x_n = r \cdot x_{n - 1} = r \cdot (r \cdot x_{n - 2} ) = r^2 \cdot x_{n - 2}

    Again, x_{n - 2} = r \cdot x_{n - 3}. Put this into the x_n =- r^2 \cdot x_{n - 2} equation. You'll get
    x_n = r^3 \cdot x_{n - 3}
    etc.

    Notice the pattern. At the "a"th step we get
    x_n = r^a \cdot x_{n - a}

    So at the nth step, we get:
    x_n = r^n \cdot x_{n - n} = r^n \cdot x_0
    your desired solution.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by theclasher View Post
    Hey everyone, I'm new here. I've taken a few classes which dealt with proofs by induction, and recently a friend came to me for help with one. I'm so rusty now though, but I know it should not be hard. The problem is to show that the solution to x-sub-n+1 = r (x-sub-n) is x-sub-n = r^n(x-sub-zero). Can anyone help solve this?
    There is nothing wrong with the answer you have already been given, but here is an alternative proof more along the lines of formal mathematical induction. The pattern for mathematical induction is this: You are given some statement about the integers which you want to prove. (1) Verify the statement for the initial case-- usually this is n=0 or n=1. (2) Assume the truth of the statement for some n greater than or equal to the initial n, then show it must also be true for n+1. The principle of mathematical induction then allows you to conclude the truth of the statement for all integers n greater than or equal to the initial n.

    So here goes: We want to show that x_n = r^n x_0 satisfies x_{n+1} = r x_n for all integers n \geq 0.

    For step 1 we need to show the statement holds for n=0. The statement we need to prove is x_0 = r^0 x_0, which is true because r^0 x_0 = x_0.

    For step 2 we assume that x_n = r^n x_0 for some n \geq 0. Then we have x_{n+1} = r x_n = r \cdot r^n x_0 = r^{n+1} x_0. This is the statement we wanted to prove for n+1, so by the principal of mathematical induction x_n = r^n x_0 for all n \geq 0.

    Hope this helps,
    jw
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Very easy proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: May 11th 2011, 11:35 AM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  3. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  4. Very Easy Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 15th 2008, 03:44 PM
  5. Probably an easy gcd proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 5th 2007, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum