I'm having trouble with a proof by induction

Question

This one should be pretty easy as its only a first year math problem. it s proof by induction that Im having trouble with.

$$let\;x_{1}=1; for\;each\;n\in \mathbb{N}\;let\;x_{n+1}=\frac{2}{3}x_{n}+1; prove\; x_{n}< 3\;for\;all\;n$$

If anyone is willing to spell it out really obviously step by step and explain how they got from one step to the next I would appreciate it a lot. Thanks.

Answer 1

Note that $x_1=1$, and $1<3$. This is the basis step, where we show it holds true for a value of $n\in \mathbb{N}$. We now move to the induction step. Assume that $x_n<3$ for some $n\in \mathbb{N}$. We now need to show the inequality holds for $x_{n+1}$. Now, since $$x_{n+1}=\dfrac{2}{3}(x_n)+1, x_n<3$$ Then $$x_{n+1}<\dfrac{2}{3}*3+1=3$$ Now we have shown that it holds true for $n+1\in \mathbb{N}$. Since we also showed it is true for a basis step $(n=1)$, and then, assuming it was true for some $n\in \mathbb{N}$, it was also true for $n+1\in \mathbb{N}$, we have shown it is true for all $x_n$.

Answer 2

First of all you need a base case, obviously $x_1 = 1 < 3$.

Inductive Hypothesis: Assume that this inequality holds for an arbitrary $n$.

Inductive step: Show that inequality for $n$ implies that it holds for $n+1$.

By our inductive hypothesis $$x_n < 3$$

now what can we do to make it look like the next element in the sequence? Multiply by $\frac{2}{3}$ and add $1$. $$\frac{2}{3}x_n +1< \frac{2}{3}3+1$$ but $\frac{2}{3}x_n+1=x_{n+1}$ by definition so $$x_{n+1}<3$$

Answer 3

So you have a sequence defined by, $$x_1 = 1 ;\ x_{n+1} = \frac{2}{3}x_n + 1,\ \forall n > 0$$ and you want to prove that the sequence is bounded by $3$.

For argument sake let's write: $$P(n):\ x_n < 3$$

Induction states: $$(P(1)\ \wedge\ (\forall n > 0\ (P(n) \implies P(n+1)))) \implies \forall n>0, \ P(n)$$.

So we need to prove two things:

• the base case: $P(1)$ ;
• the induction step: $\forall n\in \mathbb{N}\ (P(n) \implies P(n+1)$.

Let's start:

---

The base case is trivial. $x_1 = 1 < 3$.

Now, the induction step: let $n$ be number greater or equal to $1$ such that $P(n)$ holds. We need to prove $P(n+1)$.

$$x_{n+1} = \frac{2}{3}x_n + 1$$ But the induction $P(n)$ is true, so we know that $x_n < 3$ thus $\frac{2}{3}x_n < 2$. Hence, $$x_{n+1} < 3$$. We proved the base case and the induction step so we have proved: $$\forall n>0, \ P(n)$$ In other words, your sequence is bounded by $3$.

Answer 4

Here are the steps you shall take.

1. Check the base case (n=1) whether it satisfies the claim. Trivially $x_1=1<3$.
2. Now, assume the claim is true for $n=k$, i.e. $x_{k} = \frac{2}{3}x_{k-1} + 1<3$
3. Use the assumption for $n=k$ and now try to prove the claim for $n=k+1$, i.e., show that $x_{k+1} = \frac{2}{3}x_{k}+1<3$

Just need to work out the algebra (by simply plugging in).

Once you have proved the case $n=k+1$, then by induction, you have essentially proved the claim. Loosely speaking, an inductive argument works well with problems with natural number indices, such as this one with sequences. As long as you can show the claim for the next integer, you essentially established the claim for every integer, which is ultimately what you want ($x_n<3$, $\forall n$).

Answer 5

Proof by contradiction using induction.(Pierre de Fermat called this the method of infinite descent.) Suppose $x_n\geq 3$ for some $n.$ Then let $m$ be the least $n$ such that $x_n\geq 3 .$

If $m>1$ then $$x_m=(2/3)x_{m-1}+1\implies x_{m-1}=(3/2)(x_m-1)\geq (3/2)(3-1)=3$$ contrary to the definition of $m.$ But $m=1$ contradicts $x_1=1<3.$