Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.