Let the number x[itex]_{n}[/itex] be defined as follows x[itex]_{1}[/itex] = 1 and x[itex]_{2}[/itex] =2 and x[itex]_{n+2}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +[itex]_{n}[/itex]) for all n [itex]\epsilon[/itex] N. Use the principle of strong induction to show that 1[itex]\leq[/itex]x[itex]_{n}[/itex] [itex]\leq[/itex]2 for all n [itex]\epsilon[/itex] N

I have never done strong induction before so is this right?

Pf/

so P(1) is obvious

Assume true for P(1).....P(n). WTS true for P(n+1).

So P(n+1)= x[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex]). Since

x[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex])= [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]). Since its true for [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]) by our induction hypothesis its true for for n+1.

I have never done strong induction before so is this right?

Pf/

so P(1) is obvious

Assume true for P(1).....P(n). WTS true for P(n+1).

So P(n+1)= x[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex]). Since

x[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex])= [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]). Since its true for [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]) by our induction hypothesis its true for for n+1.

Last edited: