# Induction on a Sequence

This is a homework question that I am trying to use induction to solve. I am having a bit of trouble finishing the proof out:

Suppose $0 < k < 1$ and for each $n \in N$, $\langle x_n \rangle$ satisfies $|x_{n+1}|$ < $k|x_n|$.

Prove that for each $n \in N$, $|x_n| \le k^{n-1}|x_1|$

Here is what I have for my induction proof:

Base case $n = 1$: $|x_1| \le k^0|x_1| \rightarrow |x_1| = |x_1|$

Assume $|x_n| \le k^{n-1}|x_1|$

Show $|x_{n+1}| \le k^n|x_1|$

Now here is the problem I am running into... if $|x_{n+1}|$ < $k|x_n|$, how do I show $|x_{n+1}| \le k^n|x_1|$? Because $0 < k < 1$, then $k^n$ will be much less than $k$, so what stops $k^n|x_1| \le |x_{n+1}| < k|x_n|$ from being true?

-
Your case $n=1$ is wrong: if $n = 1$ you have $x_{2}$ on the left. – Rudy the Reindeer Nov 7 '11 at 9:09
I am asked to prove $|x_n| \le k^{n-1}|x_1|$, why is it $x_2$ on the left when $n = 1$? – Matt Nashra Nov 7 '11 at 9:12
You have $|x_{n+1}| < k |x_n|$ for all $x_n$. You have to use this information. So what happens if you replace $n$ with $1$? – Rudy the Reindeer Nov 7 '11 at 9:14
No, the base case is correct; the hypothesis is not used here. – Florian Nov 7 '11 at 9:14
@Matt: The base case is correct: it is the assertion $|x_n|\le k^{n-1}|x_1|$ when $n=1$. – Brian M. Scott Nov 7 '11 at 9:16

Hint: Multiply your the induction hypothesis inequality $|x_n|\le k^{n-1} |x_1|$ by $k$ on both sides.
Your induction hypothesis is that $|x_n|\le k^{n-1}|x_1|$, and you’re given that $|x_{n+1}|<k|x_n|$. Just multiply the induction hypothesis by $k$ and string the two inequalities together: $$|x_{n+1}|<k|x_n|\le k\big(k^{n-1}|x_1|\big)=k^n|x_1|\;.$$