Prove that $\frac{\phi^n}{\sqrt{5}}$ rounded off to the nearest integer gives the n'th Fibonacci number, where $\phi$ is the golden ratio.
120670
While solving , I discovered that there is a relationship between the Fibonacci sequence and the golden ratio.  After I got the correct answer via brute force, I discovered this relationship.  One of the posters said this:     The nth Fibonacci number is $[\phi^n / \sqrt{5}\;]$,  where the brackets   denote "nearest integer".       So we need $\phi^n/\sqrt{5} &gt; 10^{999}$   $n \log(\phi) - \log{5}/2 &gt; 999 \log(10)$   $n \log(\phi) &gt; 999 \log(10) + \log(5)/2$   $n &gt; (999 \log(10) + \log(5) / 2) / \log(\phi)$       A handheld calculator shows the right hand side to be 4781.8593, so   4782 is the first integer n with the desired property.   I can't quite make sense of this.  How does the poster know that the $n$-th term is $\phi^n / \sqrt{5}$?  Can you also walk me through the operations?
79559
I need to prove the following equation using mathematical induction and using the phi values if necessary.   $\phi^n = \phi F_n + \text{(another Fibonacci number)}$  In this proof, it is kind of hard for me to prove this with the part "another Fibonacci number".  Thank you in advance.  Help is much appreciated.
106823
Let $\{ F_n\}$ be the sequence of numbers defined by $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$ for $n \geq 2$. Let $f_n$ be the remainder left when $F_n$ is divided by $5$. Then $f_{2000}$ equals (A) $0$ $~~~~~~~~~~~~~~~~$ (B) $1$   $~~~~~~~~~~~~~~~~$ (C) $2$$~~~~~~~~~~~~~~~~$ (D) $3$  I found that $F(1)=1$, $F(2)=1$, $F(3)=2$, $F(4)=3$, $F(5)=5$, $F(6)=8$, $F(7)=13$, $F(8)=21$, $F(9)=34$, and $F(10)=55$. But I need a systematic pattern to find $F_n$.
35607
I was wondering why the last digit of $n^5$ is that of $n$? What's the proof and logic behind the statement? I have no idea where to start. Can someone please provide a simple proof or some general ideas about how I can figure out the proof myself? Thanks.
21412
Proof that every natural number $n\in \mathbb N$, can be written as the sum of different Fibonacci numbers between $F_2,F_3,\ldots,F_k,\ldots$.  For example: $32 = 21 + 8+3 = F_8+F_6+F_4$  Research effort:  The base step it's simple:  Let $k=1$ it can be britten as $k=1=F_2$  For the inductive step I considered:  Let $k = k  F_2 =F_2+F_2+\cdots+F_2 = \sum_{i=2}^w a_iF_i, a_i =\{0,1\} $  Then if $k$ suffice I want to see if $k+1$ suffices too... But I'm not realy seeing how to use the inductive hypothesis, so I assume It's wrong.  Any thoughts on which can the inductive step be?
62634
Let $F_n$ be the Fibonacci sequence where  $F_0$ = 0  , $F_1$ = 1 and  $F_n$ = $F_{n-1}$ + $F_{n-2}$.                   I want to prove the following by induction. $$\sum_{k=1}^{n}F_k = F_{n+2}-1$$ Here is what I have so far.  Can anybody tell me if I am right?  Base case = n=1  $F_k$ = 1 = LHS  $F_{1+2}$ - 1 = 2 - 1 = 1 = RHS  Statement is true for n=1.  Assume statement is true for n=i.  $$\sum_{k=1}^{i}F_k = F_{i+2}-1$$  Prove statement is true for n=i+1.  $$\sum_{k=1}^{i+1}F_{k} = F_{((i+1)+2)}-1$$  $F_1$ + $F_2$ +...+ $F_i$ + $F_{i+1}$ = $F_{((i+1)+2)}-1$  $F_{i+2}$ - 1 + $F_{i+1}$ = $F_{((i+1)+2)}-1$  $F_{((i+1)+2)}-1$ = $F_{((i+1)+2)}-1$  Statement holds for n=i+1
86577
How is a continuous Fibonacci number $F_n$ defined? (like the Gamma function for factorials) Tried with Binet's formula (Wiki) , but to no luck. F[n_] = N[GoldenRatio^n - 1/GoldenRatio^n]/Sqrt[5] Plot[F[n], {n, 3., 12.}, GridLines -&gt; Automatic] FibonRatio[n_] = N[Fibonacci[n + 1]/Fibonacci[n]]; Plot[{FibonRatio[n], N[GoldenRatio], 1.7}, {n, 3., 12.},   GridLines -&gt; Automatic]  Also using this continuous function definition how is it proved that $$\lim _{n\rightarrow \infty}\dfrac{F_{n+1}}{F_n} = \phi$$ ( where $\phi$ is the GoldenRatio) ? Appreciate your comments.
85502
[question:]      Prove by induction that the i th Fibonacci number satisfies the equality $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}$$where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate. [end]  I've had multiple attempts at this, the most fruitful being what follows, though it is incorrect, and I cannot figure out where I am going wrong:  [my answer:] What follows is an incorrect approach, after which comes the approach that I should have done  Inductive Hypothesis: $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}, i\in\mathbb{N}  $$   (I include 0) Base case: $$F_0=\frac{\phi^0-\hat{\phi^0}}{\sqrt5}=0$$  Proof: $$\begin{eqnarray*} F_{i+1}&amp;=&amp;\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\ &amp;=&amp;\frac{\phi*\phi^i-\hat{\phi}*\hat{\phi^i}}{\sqrt5}\\ &amp;=&amp;\frac{\frac{1+\sqrt5}{2}*\phi^i-\frac{1-\sqrt5}{2}*\hat{\phi^i}}{\sqrt5}\\ &amp;=&amp;\frac{\frac{\phi^i+\sqrt5\phi^i}{2}-\frac{\hat{\phi^i}-\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\ &amp;=&amp;\frac{\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\ &amp;=&amp;\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2*\sqrt5}\\ &amp;=&amp;\frac{1}{2}\left(\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{\sqrt5}\right)\\ &amp;=&amp;\frac{1}{2}\left(\frac{\sqrt5\phi^i}{\sqrt5} + \frac{\sqrt5\hat{\phi^i}}{\sqrt5} +\frac{\phi^i-\hat{\phi^i}}{\sqrt5}\right)\\ &amp;=&amp;\frac{1}{2}\left(\phi^i+\hat{\phi^i}+F_{i}\right)\text{   by inductive hypothesis}\\ &amp;=&amp;\frac{1}{2}\left(\sqrt5*...\right)\\ \end{eqnarray*}$$ Actually I just saw my error in that line (I eventually multiplied by $\frac{\sqrt5}{\sqrt5}$ and  substituted for $F_i$, but I see that the conjugates are added there, not subtracted).  Correct approach: $$\begin{eqnarray*} F_{i+1}&amp;=&amp;F_{i} + F_{i-1}\\ &amp;=&amp;\frac{\phi^i-\hat{\phi^i}}{\sqrt5}+\frac{\phi^{i-1}-\hat{\phi^{i-1}}}{\sqrt5}\\ &amp;=&amp;\frac{\left(\phi+\hat{\phi}\right)\left(\phi^i-\hat{\phi^i}\right)-\phi\hat{\phi}\left(\phi^{i-1}-\hat{\phi^{i-1}}\right)}{\sqrt5}\text{ (see answer for why this works)}\\ &amp;=&amp;\frac{\phi^{i+1}-\phi\hat{\phi^i}+\hat{\phi}\phi^i-\hat{\phi^{i+1}}-\phi^i\hat{\phi}+\phi\hat{\phi^i}}{\sqrt5}\\ &amp;=&amp;\frac{\phi^{i+1}-\hat{\phi^{i+1}}-\phi\hat{\phi^i}+\phi\hat{\phi^i}-\hat{\phi}\phi^i+\hat{\phi}\phi^i}{\sqrt5}\\ &amp;=&amp;\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\ \text{Q.E.D., punk problem.} \end{eqnarray*}$$  From what I searched on the web, there is no available source proving this of the Fibonacci sequence - all inductive hypothesis proofs prove the actual sequence with induction.   Bill, it's always easy to forget about the inherent properties of special numbers... I didn't even realize $\phi$ + $\hat{\phi}$ = 1 in your first hint, as well as the multiplication, until you pointed it out. Alex, I'm sure that going through the problem that way will produce the result, also, but with Bill's, it's much faster.    Thanks for the help.
55299
Let $f(n)$ denote the number of sequences $a_1, a_2, \ldots, a_n$ that can be constructed where each $a_i$ is $+1$, $-1$, or $0$.  Note that no two consecutive terms can be $+1$, and no two consecutive terms can be $-1$. Prove that $f(n)$ is the nearest integer to $\frac12(1+\sqrt2)^{n+1}$.  Can anyone help me with this problem. I really do not know what to do in this one.
117645
Prove that the inequality $$\left|\frac{m}{n}-\frac{1+\sqrt{5}}{2}\right|&lt;\frac{1}{mn}$$ holds for positive integers $m, n$ if and only if $m$ and $n$ where $m &gt; n$ are two successive terms of the Fibonacci sequence.   I thought about using the explicit formula for the Fibonacci sequence, which is $$F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right),$$ but this seems to get computational. Is there an easier way to think about this?
45335
I'm already aware of the Binet formula $\displaystyle F_n = \frac{\varphi^n + \frac{1}{\varphi^n}}{\sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:  $$ F_n\sqrt{5} = \varphi^n + \frac{1}{\varphi^n}\\ \varphi^nF_n\sqrt{5} = \varphi^{2n} + 1\\ \varphi^{2n} - \varphi^nF_n\sqrt{5}+ 1 = 0\\ \varphi^n = \frac{F_n\sqrt{5}+ \sqrt{5F_n^2 - 4}}{2}\\ n = \log_\varphi\left(\frac{F_n\sqrt{5}+ \sqrt{5F_n^2 - 4}}{2}\right) $$  But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:  $$ n = \log_\varphi\left(\frac{F_n\sqrt{5}+ \sqrt{5F_n^2 + 4(-1)^n}}{2}\right) $$  But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:  $$ \varphi^{2n} - \varphi^nF_n\sqrt{5} = (-1)^n $$  Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.  As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.  Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.
9047
Prove that if $\phi$ is not equal to $2k\pi$ for any integer $k$, then  $$\sum_{t=0}^{n} \sin{(\theta + t \phi)}=\frac{\sin({\frac{(n+1)\phi}2})\sin{(\theta+\frac{n \phi}2)}}{\sin{(\frac{\phi}2)}}$$  Find a similar formula for  $$\sum_{t=0}^{n}\cos{(\theta+t\phi)}$$  where the functions sin and cos appear on the right-hand side.  Find, for all $\theta$, the values of   $$\sum_{t=0}^{n}\cos^{2}{(2t\theta)}$$ and $$\sum_{t=0}^{n}\sin^{2}{(2t\theta)}$$
25667
DISCLAIMER: I do not deal with in-depth mathematics on a daily basis as some of you may, so please pardon my ignorance or lack of coherence on this topic.  QUESTION: What is the significance of starting the Fibonacci sequence with $0,1$ ?  For instance, if I picked any two random integers, say 2 and 7, to start a sequence would I actually be creating some multiple or derivation of the Fibonacci sequence?  Is there a general mathematical explanation for the relationship between any sequence represented by $a[0] = x, a[1] = y, a[n] = a[n-1] + a[n-2]$ and the Fibonacci sequence?  Or, back to my example sequence, is there a general mathematical relationship between:  $2,7,9,16,25,41,66,107,173,280...$  and  $0,1,1,2,3,5,8,13,21,34...$  Perhaps the Golden Ratio explains it somehow?  Any help would be appreciated.
74716
I was looking at the Fibonacci sequence:  $$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,\ldots, F_n : F_n + F_{n - 1} = F_{n + 1} \land F_0 = 0$$  Here I noticed something; $\qquad F_n^2 + F_{n\pm1}^2 = F_{2n\pm1} : n\in \mathbb{N}$  For example; $$\ \ F_3^2 + F_{3 + 1}^2 = F_3^2 + F_4^2 = 2^2 + 3^2 = F_{2\times3 + 1} = F_{6 + 1} = F_7 = 13$$ $$F_3^2 + F_{3 - 1} = F_3^2 + F_2^2 = 2^2 + 1^2 = F_{2\times3 - 1} = F_{6 - 1} = F_5 = 5$$ However, no matter how true this can seem, I cannot seem to prove/disprove it.    My Attempt: $$\because (a + b)^2 = (a + b)(a + b) = a^2 + ab + ba + b^2 = a^2 + b^2 + 2ab : (a,b)\in \mathbb{Z}$$ $$\implies F_n^2 + F_{n\pm 1}^2 = (F_n + F_{n\pm 1})^2 - 2F_nF_{n\pm 1}$$ $$\implies F_n^2 + F_{n - 1}^2 = F_{n + 1}^2 - 2F_nF_{n - 1} : F_n + F_{n - 1} = F_{n + 1}$$ $$\implies F_n^2 + F_{n + 1}^2 = F_{n + 2}^2 - 2F_nF_{n + 1} : F_n + F_{n + 1} = F_{n + 2} \iff F_n + F_{n - 1} = F_{n + 1}$$ $$\implies F_{2n\pm 1} + 2F_nF_{n\pm 1} = F_{n + 2\lor1}^2 : F_n^2 + F_{n\pm 1}^2 = F_{2n\pm 1} \tag{+2 if +, +1 if -}$$ $$\implies F_{2n\pm 1} + 2\sqrt{F_{2n\pm 1} - F_{n\pm 1}^2}\sqrt{F_{2n\pm 1} - F_n^2}= F_{n + 2\lor1}$$ $$\implies F_{2n\pm 1} + 2\sqrt{(F_{2n\pm 1} - F_{n\pm 1}^2)(F_{2n\pm 1} - F_n^2)} = F_{n + 2\lor1}^2$$ $$\implies F_{2n\pm 1} + 2\sqrt{F_{2n\pm 1}(F_{2n\pm 1} - F_n^2 - F_{n\pm 1}^2) - (F_nF_{n\pm 1})^2} = F_{n + 2\lor1}^2$$.  $$\because F_n^2 + F_{n\pm 1}^2 = F_{2n\pm 1}$$ $$\implies F_{2n\pm 1} + 2\sqrt{-(F_nF_{n\pm 1})^2} = F_{n + 2\lor1} \neq F_{2n\pm 1} + 2\sqrt{\big(-(F_nF_{n\pm 1})\big)^2}$$ $$\therefore F_{2n\pm 1} + 2F_nF_{n\pm 1}i = F_{n + 2\lor1} : i = \sqrt{-1}$$  I have looked over every step and cannot see where I am wrong. The only part that must be wrong is that:  $$F_{2n\pm 1} + 2F_nF_{n\pm 1}i = F_{n + 2\lor1} \iff F_n^2 + F_{n\pm1}^2 = F_{2n\pm 1}$$  I can seperate $F_{2n\pm 1}$ as $F_n^2 + F_{n\pm 1}^2$ (if true) so I turn the equation into:  $$F_n^2 + F_{n\pm 1}^2 + 2F_nF_{n\pm 1}i = F_{n + 2\lor1}$$ $$\therefore (F_n + F_{n\pm 1})\bigg(\frac{F_n}{F_{n\pm 1}} + \frac{F_{n\pm 1}}{F_n} + 2i\bigg) = F_{n + 2\lor1}$$ Now I know that the greater the value of $n$, one of the fractions in the above equation (depending on which sign is used in $F_{n\pm 1}$) will get closer to the golden ratio $φ = \frac{1 + \sqrt{5}}{2}$ but $i = \sqrt{-1}$ is not a "real" number, although $F_n$ is.  I then searched for other formulae for finding $F_n$ and came across the one below (being Binet's Formula):  $$F_n = \bigg\{\frac{φ^n - ψ^n}{φ - ψ} : ψ = φ - \frac{\sqrt{20}}{2} = \frac{1 - \sqrt{5}}{2} \ \land \ φ - ψ = \sqrt{5}\bigg\}$$  But I do not know what how to turn that into $F_{n\pm 1}$. Could you please show me where I went wrong (because I must have gone wrong somewhere), and also if you wish, could you please show me how to turn the above fraction into $F_{n\pm 1}$ (if possible).  I only used the $(a + b)^2$ expansion rule because my skill level in mathematics is not particularly high compared to most of the users on this site (especially when logging into the MSE and finding fancy symbols like $\nabla$ and $\partial$ and $\sum$ which all look Greek to me, however the only "fancy" thing I know is that $i = i^5 = \cdots = \sqrt{-1}$) so if you used any other techniques in trying to prove this formula, could you please show me step by step?  Much appreciated. Thank you in advance.    Edit: I believe this question is a duplicate of this other question $\longrightarrow$   and I can go here to serve as a little hint $\longrightarrow$
81416
I know that there is a similar post, but I 'm trying a different proof. I will write $P$  for the set of all positive prime numbers. Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$. Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$ So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where  $n_1,n_2,n_3 \in \mathbb{Z}^+$. So, \begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4  \tag{*} \end{align*} The possible cases for $n_i$ are:  $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively $n_2=1 \implies \phi(3)=2$ $n_3=1 \implies \phi(5)=4$  All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$ Is this completely right? Thank you.
55152
Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?
58309
I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions.  The way I am tackling this is by constructing all combinations of prime powers such that when passed to Euler's function will yield $6$.  For example, I know that $\phi(7)=6$, $\phi(3^2)=6$, and $\phi(2)=1$. Therefore, the numbers should be $7$, $7\cdot2=14$, $3^2=9$, and $3^2\cdot2=18$.  I believe that there cannot possibly be any others because of the way the $\phi$ function is defined. What do you guys think?