# 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
$\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$

-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 $\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