0
$\begingroup$

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?

  • 0
    @Matt: The base case is correct: it is the assertion $|x_n|\le k^{n-1}|x_1|$ when $n=1$.2011-11-07

2 Answers 2

1

Hint: Multiply your the induction hypothesis inequality $|x_n|\le k^{n-1} |x_1|$ by $k$ on both sides.

1

Your induction hypothesis is that $|x_n|\le k^{n-1}|x_1|$, and you’re given that $|x_{n+1}|. Just multiply the induction hypothesis by $k$ and string the two inequalities together: $|x_{n+1}|