# Thread: Easy proof by induction

1. ## 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?

2. Originally Posted by theclasher
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$

-Dan

3. Originally Posted by theclasher
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