Prev: is H_s an algebra?
Next: -> Higher Infinities
From: jaialai technology on 19 Jun 2010 09:36
I am trying to rebuild my rusty proof by induction skills...
We want to show for the fibonacci terms F_n n>=6 that F_n >=
2^(0.5n).
Proof:
(i) Basis step
If k=6 then F_6=8 and 2^(0.5(6))=2^3=8
(ii) Assume that for any k>=6 then F_k >= 2^(0.5k)
(iii) Want to show this F_(k+1) >= 2^(0.5(k+1))
F_(k+1)=F_k + F_(k-1)
From (ii) we know F_k >= 2^(0.5k) and F_(k-1) >= 2^(0.5k-1)
so
F_(k+1) >= 2^(0.5k) + 2^(0.5k-1)
F_(k+1) >= (1.5)*2^(0.5k)

Since 2^(0.5(k+1))=2^(0.5k+.5)=2^(0.5k) * sqrt(2)
and 1.5 > sqrt(2)
then F_(k+1) >= 2^(0.5(k+1)) and the proof is complete.

Is this correct?
From: hagman on 19 Jun 2010 13:01
On 19 Jun., 15:36, jaialai technology <jaialai.technol...(a)gmail.com>
wrote:
> I am trying to rebuild my rusty proof by induction skills...
> We want to show for the fibonacci terms F_n  n>=6 that F_n >=
> 2^(0.5n).
> Proof:
>     (i) Basis step
>            If k=6 then F_6=8 and 2^(0.5(6))=2^3=8
>     (ii) Assume that for any k>=6 then F_k >= 2^(0.5k)
>     (iii) Want to show this F_(k+1) >= 2^(0.5(k+1))
>           F_(k+1)=F_k + F_(k-1)
>           From (ii) we know F_k >= 2^(0.5k) and F_(k-1) >= 2^(0.5k-1)
> so
>           F_(k+1) >= 2^(0.5k) + 2^(0.5k-1)
>           F_(k+1) >= (1.5)*2^(0.5k)
>
>           Since 2^(0.5(k+1))=2^(0.5k+.5)=2^(0.5k) * sqrt(2)
>           and 1.5 > sqrt(2)
>           then F_(k+1) >= 2^(0.5(k+1)) and the proof is complete.
>
> Is this correct?

Not completely.
Your induction step would want to show F_7 >= 2^(0.5*7) from
F_6 >= 2^(0.5*6) and F_5 >= 2^(0.5*5).
However, F_5 = 5 < 2^(0.5*5) ~ 5.66.
In fact, also F_7 < 2^(0.5*6) + 2^(0.5*5).

For Fibonacci-related induction proofs it is often convenient to show
"For all k >= n, we have Phi( k, F_k )"
by showing
1) Phi( k, F_k )
2) Phi( k+1, F_{k+1} )
3) If k>=n and Phi( k, F_k ) and Phi( k+1, F_{k+1} ), then Phi( k+2,
F_{k+2} )

hagman
 | 
Pages: 1
Prev: is H_s an algebra?
Next: -> Higher Infinities