Results 1 to 3 of 3

Thread: 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
    11,152
    Thanks
    731
    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
    $\displaystyle x_{n + 1} = r \cdot x_n$

    and verify it has the solution
    $\displaystyle 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 $\displaystyle 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.

    $\displaystyle x_n = r \cdot x_{n - 1}$

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

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

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

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

    So at the nth step, we get:
    $\displaystyle 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 $\displaystyle x_n = r^n x_0$ satisfies $\displaystyle x_{n+1} = r x_n$ for all integers $\displaystyle n \geq 0$.

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

    For step 2 we assume that $\displaystyle x_n = r^n x_0$ for some $\displaystyle n \geq 0$. Then we have $\displaystyle 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 $\displaystyle x_n = r^n x_0$ for all $\displaystyle 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: Mar 8th 2009, 09:33 PM
  3. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  4. Very Easy Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 15th 2008, 03:44 PM
  5. Probably an easy gcd proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 5th 2007, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum