Fibonacci
- Thread starter gpenguin
- Start date
I had to do this same problem way back when. Here's a start.
Case for n=1: \(\displaystyle f_{1}\leq \frac{7}{4}\Rightarrow 1\leq \frac{7}{4}......\text{True}\)
Assume true for \(\displaystyle f_{k}\leq \left(\frac{7}{4}\right)^{k}\), then true for \(\displaystyle f_{k+1}\leq \left(\frac{7}{4}\right)^{k+1}\)
\(\displaystyle f_{k}+f_{k-1}=f_{k+1}\).
\(\displaystyle \left(\frac{7}{4}\right)^{k}+\left(\frac{7}{4}\right)^{k-1}\leq \left(\frac{7}{4}\right)^{k+1}\)
\(\displaystyle \left(\frac{7}{4}\right)^{k}+\frac{4}{7}\left(\frac{7}{4}\right)^{k}\leq \left(\frac{7}{4}\right)^{k+1}\)
Can you finish with the induction.
Case for n=1: \(\displaystyle f_{1}\leq \frac{7}{4}\Rightarrow 1\leq \frac{7}{4}......\text{True}\)
Assume true for \(\displaystyle f_{k}\leq \left(\frac{7}{4}\right)^{k}\), then true for \(\displaystyle f_{k+1}\leq \left(\frac{7}{4}\right)^{k+1}\)
\(\displaystyle f_{k}+f_{k-1}=f_{k+1}\).
\(\displaystyle \left(\frac{7}{4}\right)^{k}+\left(\frac{7}{4}\right)^{k-1}\leq \left(\frac{7}{4}\right)^{k+1}\)
\(\displaystyle \left(\frac{7}{4}\right)^{k}+\frac{4}{7}\left(\frac{7}{4}\right)^{k}\leq \left(\frac{7}{4}\right)^{k+1}\)
Can you finish with the induction.
\(\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\)
Do you have to use induction?. This proof can be done by using determinants of matrices.
But, going with induction.
We have to show that if \(\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\) is true, then
\(\displaystyle f_{n+2}f_{n}-f_{n+1}^{2}=(-1)^{n+1}\) is true as well.
I will skip the n=1 case and all that.
Start with:
\(\displaystyle f_{n+1}\underbrace{\left(f_{n+1}-f_{n}\right)}_{\text{f(n-1)}}-f_{n}^{2}=(-1)^{n}\).
\(\displaystyle f_{n+1}^{2}-f_{n}f_{n+1}-f_{n}^{2}=(-1)^{n}\)
\(\displaystyle f_{n+1}^{2}-f_{n}\underbrace{\left(f_{n+1}+f_{n}\right)}_{\text{f(n+2)}}=(-1)^{n}\)
\(\displaystyle f_{n+1}^{2}-f_{n}f_{n+2}=(-1)^{n}\)
\(\displaystyle f_{n}f_{n+2}-f_{n+1}^{2}=-(-1)^{n}\)
\(\displaystyle f_{n+2}f_{n}-f_{n+1}^{2}=(-1)^{n+1}\)
To use the determinant method:
\(\displaystyle \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n}=\begin{pmatrix}f_{n+1}&f_{n}\\f_{n}&f_{n+1}\end{pmatrix}\)
Take the determinant of both sides. If two square matrices have the same size, then \(\displaystyle det(AB)=det(A)\cdot det(B)\)
Do you have to use induction?. This proof can be done by using determinants of matrices.
But, going with induction.
We have to show that if \(\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\) is true, then
\(\displaystyle f_{n+2}f_{n}-f_{n+1}^{2}=(-1)^{n+1}\) is true as well.
I will skip the n=1 case and all that.
Start with:
\(\displaystyle f_{n+1}\underbrace{\left(f_{n+1}-f_{n}\right)}_{\text{f(n-1)}}-f_{n}^{2}=(-1)^{n}\).
\(\displaystyle f_{n+1}^{2}-f_{n}f_{n+1}-f_{n}^{2}=(-1)^{n}\)
\(\displaystyle f_{n+1}^{2}-f_{n}\underbrace{\left(f_{n+1}+f_{n}\right)}_{\text{f(n+2)}}=(-1)^{n}\)
\(\displaystyle f_{n+1}^{2}-f_{n}f_{n+2}=(-1)^{n}\)
\(\displaystyle f_{n}f_{n+2}-f_{n+1}^{2}=-(-1)^{n}\)
\(\displaystyle f_{n+2}f_{n}-f_{n+1}^{2}=(-1)^{n+1}\)
To use the determinant method:
\(\displaystyle \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n}=\begin{pmatrix}f_{n+1}&f_{n}\\f_{n}&f_{n+1}\end{pmatrix}\)
Take the determinant of both sides. If two square matrices have the same size, then \(\displaystyle det(AB)=det(A)\cdot det(B)\)
gpenguin said:
I would stay with the methods shown by galactus for this solution.
If you are allowed to know that \(\displaystyle F(n) \ = \ \frac{(1.618...)^n - (-0.618...)^n}{\sqrt{5}} *\)
from http://en.wikipedia.org/wiki/Fibonacci_number, as one of the places to read it, then
\(\displaystyle F(n) \ < \ \frac{(1.618...)^n + (1.618...)^n}{\sqrt{5}} ** \ = \ \frac{2(1.618...)^n}{\sqrt{5}} \ < \ 0.5(1.618...)^n \ < (1.75)^n \ =\ \bigg(\frac{7}{4}\bigg)^n\)
\(\displaystyle Note: \ \ Not \ only \ does \ the \ difference, \ \bigg(\frac {7}{4}\bigg)^n - \ F(n), \ gets \ larger \ with \ larger \ n,\)
\(\displaystyle but \ also \ the \ ratio, \ \frac{(7/4)^n}{F(n)}, \ gets \ larger \ with \ larger \ n.\)
\(\displaystyle A \ justification \ could \ be \ added \ for \ going \ to \ ** \ from \ *.\)
Hello, gpenguin!
For reference:
. . \(\displaystyle \begin{array}{c||ccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & \hdots \\ \hline F_n & 1 & 1 & 2 & 3 & 5 & 8 & \hdots \end{array}\)
\(\displaystyle \text{Verify }S(2):\;F_3\!\cdot\!F_1 - (F_2)^2 \;=\;(2)(1) - 1^2 \:=\
\text{-}1)^2 \quad\hdots\text{ True.}\)
\(\displaystyle \text{Assume }S(k): \;F_{k+1}\!\cdot\!F_{k-1} - (F_k)^2 \;=\;(\text{-}1)^k\)
\(\displaystyle \text{The left side of }S(k\!+\!1)\text{ is: }\;F_{k+2}\!\cdot\!F_k - (F_{k+1})^2\)
\(\displaystyle \text{Replace }F_{k+2}\text{ with }(F_k +F_{k+1}):\)
. . \(\displaystyle (F_k+F_{k+1})\!\cdot\!F_k - (F__l+1})^2\)
. . \(\displaystyle =\; (F_k)^2 + F(k)\!\cdot\!F_{k+1} - (F_{k+1})^2\)
. . \(\displaystyle =\;(F_k)^2 - F_{k+1}\underbrace{\left[F_{k+1} - F_k\right]}_{\text{This is }F_{k-1}}\)
. . \(\displaystyle =\;(F_k)^2 - F_{k+1}\!\cdot\!F_{k-1}\)
. . \(\displaystyle =\;-1\,\underbrace{\bigg[F_{k+1}\!\cdot\! F_{k-1} - (F_k)^2\bigg]}_{\text{This is }S(k)}\)
. . \(\displaystyle =\;-1(\text{-}1)^k \;=\;(\text{-}1)^{k+1}\)
\(\displaystyle \text{We have proved }S(k+1)\!:\;\;F_{k+2}\!\cdot\!F_k - (F_{k+1})^2 \;=\; (\text{-}1)^{k+1}\)
. . . . \(\displaystyle \text{ta-}DAA!\)
For reference:
. . \(\displaystyle \begin{array}{c||ccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & \hdots \\ \hline F_n & 1 & 1 & 2 & 3 & 5 & 8 & \hdots \end{array}\)
\(\displaystyle \text{Verify }S(2):\;F_3\!\cdot\!F_1 - (F_2)^2 \;=\;(2)(1) - 1^2 \:=\
\text{-}1)^2 \quad\hdots\text{ True.}\)\(\displaystyle \text{Assume }S(k): \;F_{k+1}\!\cdot\!F_{k-1} - (F_k)^2 \;=\;(\text{-}1)^k\)
\(\displaystyle \text{The left side of }S(k\!+\!1)\text{ is: }\;F_{k+2}\!\cdot\!F_k - (F_{k+1})^2\)
\(\displaystyle \text{Replace }F_{k+2}\text{ with }(F_k +F_{k+1}):\)
. . \(\displaystyle (F_k+F_{k+1})\!\cdot\!F_k - (F__l+1})^2\)
. . \(\displaystyle =\; (F_k)^2 + F(k)\!\cdot\!F_{k+1} - (F_{k+1})^2\)
. . \(\displaystyle =\;(F_k)^2 - F_{k+1}\underbrace{\left[F_{k+1} - F_k\right]}_{\text{This is }F_{k-1}}\)
. . \(\displaystyle =\;(F_k)^2 - F_{k+1}\!\cdot\!F_{k-1}\)
. . \(\displaystyle =\;-1\,\underbrace{\bigg[F_{k+1}\!\cdot\! F_{k-1} - (F_k)^2\bigg]}_{\text{This is }S(k)}\)
. . \(\displaystyle =\;-1(\text{-}1)^k \;=\;(\text{-}1)^{k+1}\)
\(\displaystyle \text{We have proved }S(k+1)\!:\;\;F_{k+2}\!\cdot\!F_k - (F_{k+1})^2 \;=\; (\text{-}1)^{k+1}\)
. . . . \(\displaystyle \text{ta-}DAA!\)