Proof by Induction that if $s_1 < s_2$ and $s_{n+1} = \frac{s_{n+1} + s_n}{2}$ then $s_1 < s_n < s_3$ for all $n \ge 3$

115 Views Asked by At

Suppose$$s_1 < s_2$$ Use induction to show if $$s_{n+1} = \frac{s_{n+1}+s_{n}}{2}$$ for all $$n \geq 1$$ then: $$s_1< s_n < s_2, \ n \geq 3$$

I have no idea how to do this. I tried induction. Did the base step, but have no idea what the inductive step could be.

1

There are 1 best solutions below

1
On

We will show, using strong induction, that if $s_1\lt s_2$ and $$s_{n+1}=\frac{s_n+s_{n-1}}{2}$$ then $s_1\lt s_n\lt s_2$ for all $n\ge 3$.

Comment: We changed the definition of $s_{n+1}$ from the OP's $s_{n+1}=\frac{s_{n+1}+s_n}{2}$. That ebersion would imply that $s_{n+1}=s_n$, leaving a rather dull sequence.)

Let's check the base case (it could actually be skipped). There are two things to prove: (i) $s_1\lt s_3$ and (ii) $s_3\lt s_2$.

To prove $s_1\lt s_3$, we calculate the difference $s_3-s_1$. This is $\frac{s_2+s_1}{2}-s_1$. That simplifies to $\frac{s_2-s_1}{2}$, which is positive, so $s_1\lt s_3$.

I will leave showing that $s_3\lt s_2$ to you.

Now we show that if the result is true for all $n\le k$, then it is true for $n=k+1$. So we want to prove that $$s_1\lt s_{k+1}\lt s_2.$$ We show that $s_{k+1}\lt s_2$, and leave it to you to prove the other inequality.

So we want to show that $s_2-\frac{s_k+s_{k-1}}{2} \gt 0$.

Equivalently, we want to show that $2s_2-(s_k+s_{k-1})\gt 0$. Note that $$2s_2-(s_k+s_{k-1})= (s_2-s_k)+(s_2-s_{k-1}).$$ By the induction hypothesis, each of $s_2-s_k$ and $2-s_{k-1}$ is $\ge 0$, and one of them is $\gt 0$ (if $k=3$, then $k-1=2$, so $2-s_{k-1}=0$.) Thus their sum is $\gt 0$. This completes the proof.