# Thread: Proof using principle of strong induction

1. ## Proof using principle of strong induction

Let the numbers x_n be defined as follows: x_1≔1, x_2≔2, and x_(n+2)=(1/2)((x_(n+1))+(x_n)) for all n∈N. Use the Principle of Strong Induction to show that 1 ≤ x_n ≤ 2 for all n∈N.

2. Here is a generic outline. It may seem obvious, but it is indispensable, and since you have not indicated where your difficulty lies, it is better to start there.

1. Represent your problem as "for all n∈N, P(n)". Here P(n) is the induction statement, also called induction hypothesis in the case of regular (not strong) induction. Note that it depends on n and for each given n it is a proposition, i.e., it is either true or false. In particular, P(n) is not a number.

2. Prove "for all n, P(0), ..., P(n - 1) imply P(n)". This is inductive step. For this, fix an arbitrary n and assume all of P(0), ..., P(n - 1). From here, try to prove P(n).

Consider step 2 in more detail. Let's fix n. If n = 0, then the list P(0), ..., P(n - 1) is empty. This means that P(0) has to be proved from scratch, without any assumptions. When n = 1, you assume P(0) and use it to prove P(1). For n = 2, you assume P(0) and P(1) and prove P(2), etc.

Hint: Here it is enough to have two induction statements P(n - 2) and P(n - 1) as the hypothesis in the inductive step. Note, however, that this does not work for all n. When n = 1, n - 2 is not a natural number. As noted above, to prove P(1) one can only rely on P(0). Thus, for this problem, inductive step can be formulated this way: Prove P(0), then prove P(1) assuming P(0), and for all n >= 2, prove P(n) assuming P(n - 2) and P(n - 1). This last part can be reformulated as follows: for all n >= 0, prove P(n + 2) assuming P(n) and P(n + 1).

3. Can we restate the problem.

If $\displaystyle x_1:=1,\,x_2=2$ then proove that for all $\displaystyle n>2$ is $\displaystyle x_n=\frac{x_{n-1}+x_{n-2}}{2}\in [1,2].$

In case of $\displaystyle n_0=3$ the property is obviously true: $\displaystyle x_3=\frac{2+1}{2}=\frac{3}{2}\in[1,2].$.

For arbitrary $\displaystyle k>n_0$ the stated property is true for all $\displaystyle n$ such that $\displaystyle n_0\leq n \leq k$ because

$\displaystyle x_{n}=\frac{\overbrace{\overbrace{x_{n-1}}^{\in [1,2]}+\overbrace{x_{n-2}}^{\in [1,2]}}^{\in[2,4]}}{2}\in[1,2]$.

So it is true for the case $\displaystyle k+1$. Hence the statement is true for all $\displaystyle n\in\mathbb{N}$

How does this seem?

4. The math (inequalities about the arithmetic mean) behind this problem is pretty easy. However, the logic has to be expressed precisely.

In case of $\displaystyle n_0=3$ the property is obviously true: $\displaystyle x_3=\frac{2+1}{2}=\frac{3}{2}\in[1,2]$.
There is no need to consider $\displaystyle x_3$ separately because it is covered by the inductive step.

For arbitrary $\displaystyle k>n_0$ the stated property is true for all $\displaystyle n$ such that $\displaystyle n_0\leq n \leq k$ because
This is not something to be proved. The fact that the induction statement is true for all precedent n is assumed in the inductive step.

So it is true for the case $\displaystyle k+1$.
It is not clear how this follows because your argument above does not mention k+1.

5. I was trying my best to fit my logic according to this. My reasoning was that if you prove that the induction basis $\displaystyle P(n_0)$ is true, and if you prove that for any $\displaystyle k>n_0$ the statement $\displaystyle P(n)$ is true for all $\displaystyle n_0\leq n \leq k$ then it follows that it is true for all $\displaystyle n\in \mathbb{N}$.

Thus the statement is true up to "index" $\displaystyle k$ which can be arbitrarily large natural number, so it has to be true for all natural numbers.

If something is wrong with this reasoning please let me know exactly what is wrong so I will know better in the future.

6. MathoMan, in both of your posts, something is not clear about the inductive step. Namely, I am not sure what the induction hypothesis and the goal are.

In the link you gave, the inductive step for any number k proceeds as follows: Assume P(n) for all n0 <= n <= k (induction hypothesis) and prove P(k + 1) (goal). On the other hand, in your first post you seem to fix k and then prove (not assume) P(n) for all n0 <= n <= k. In doing that, it is not clear what hypothesis you rely on.

In your second post, you again say that the person using induction is supposed to prove, for any given k, that P(n) holds for all n such that $\displaystyle n_0\leq n \leq k$. Of course, if one proves that, it trivially follows that P(k) is true for all $\displaystyle k\in\mathbb{N}$: since, for any k, P(n) holds for all $\displaystyle n_0\leq n \leq k$, in particular, P(k) holds. However, the main idea of induction is not to prove P(n) for all n0 <= n <= k, or even its special case P(k), in one step. One breaks the proof of P(k) into k steps and uses the results of the previous steps (proofs of P(0), ..., P(k - 1)) to show P(k).

7. I appreciate your replies. So you say that I should assume that for n such that 2<=n<=k all numbers x_n are in[1,2]. Ok so induction step remains trivial to prove using the same logic used in my earlier post. By induction hypothesis both x_k and x_(k-1) are in[1,2] hence their arithmetic mean which is x_(k+1) also has to be in [1,2].

Is that better?
Sorry, I'm typing on my iPhone and that's why there's no TeX.

8. Yes, that's fine.