The Fibonacci numbers are defined as follows: $f_0 = 0,\ f_1 = 1$, and for $n ≥ 2,\ f_n = f_{n−1} +f_{n−2}$. Prove that for every positive integer $n$,  $$f_3 + f_6 + \ldots + f3_n = \frac{1}{2} (f_{3n+2} - 1) $$  Here are my steps:  Basis Step:  For $n ≥ 1$  $f_{3\cdot1} = \frac{1}{2} (f_{3\cdot 1+2} - 1) $  LHS $= f_3 = 2$  RHS $= \frac{1}{2} (f_5 - 1) =  \frac{1}{2} (5 – 1) = 2$  Induction Step:  Assume that $f_3 + f_6 + \ldots + f_{3n} = \frac{1}{2} (f_{3n+2} - 1)$  for some $n ≥ 1$.  Show that $f_3 + f_6 + \ldots + f_{3n}  + f_{3(n+1)} = \frac{1}{2} (f_{3(n+1)+2} – 1)$.  $$\frac{1}{2} (f_{3n+2} – 1) = \frac{1}{2} (f_{3(n+1)+2} – 1) + f_{3(n+1)}\ \text{(Basis)}\\ \text{LHS}=\frac{1}{2}(f_{3n+5}-1)+f_{3n+3}$$  I don't know how to proceed further. I understand what I have to do, but I don't know where to start reducing it using the fib definition.
121445
Prove the following:  $$f_3+f_6+...f_{3n}= \frac 12(f_{3n+2}-1) \\ $$  For $n \ge 2$  Well I got the basis out of the way, so now I need to use induction: So that $P(k) \rightarrow P(k+1)$ for some integer $k \ge 2$  So, here are my first steps:  $$ \begin{align} &amp; \frac 12(f_{3k+2}-1) + f_{3k+3} = \\     &amp; = \frac 12(f_{3k+2}-1) + f_{3k+1} + f_{3k} +  f_{3k+1} \\    &amp; = \frac 12(f_{3k+2}-1) + f_{3k+1} + \frac 12(f_{3k+2}-1) +  f_{3k+1} \\    &amp; = f_{3k+2}-1 + 2 \cdot f_{3k+1}     \end{align} $$  And the fun stops around here. I don't see how to get to the conclusion: $\frac 12(f_{3k+5}-1) \\ $. Any help from this point would be great.
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$.
37972
I have a Fibonacci problem ... basically I have to show that:  $$F(n+2) = 1 + \sum_{i=0}^{n} F(i)$$  Using strong induction, I must now show that:  $$F(n+2) = F(n+1) + F(n)$$ $$F(n+2) = (1 + \sum_{i=0}^{n-1} F(i)) + (1 + \sum_{i=0}^{n-2} F(i))$$ $$F(n+2) = 2 + \sum_{i=0}^{n-1} F(i) +  \sum_{i=0}^{n-2} F(i)$$    How do I add these two summations to show that they equal the first equation (at the top)?  Please provide the steps with explanation as to what you are doing. Thanks
102133
I am trying to prove the follwowing: $$\sum_{k=0}^n F_kF_{n-k}=\sum_{k=0}^n(k+1)F_{k+1}(-2)^{n-k}$$  where $F_k = F_{k-1} + F_{k-2}$ with $F_0 = F_1=1$ are the Fibonacci numbers.  Now the left hand side of the identity is simply the cauchy product of the $n$-th coefficient of the generating function multiplied by itself, meaning the $n$-th coefficient of  $$F(z)\cdot F(z)$$ where $F(z)=\sum_{k\ge 0} F_k z^k$. I am not sure however, if this insight really helps a lot. The only thing I know about the coefficients are its explicit form $$F_k=\sum_{k\ge 0}\binom{n-k}{k}$$ but this did not lead to any results as I would be left with  $$\sum_{k=0}^n F_kF_{n-k}=\sum_{k=0}^n\sum_{l\ge 0 }\binom{n-l}{l}\sum_{j\ge 0}\binom{n-j}{j}$$  I would appreciate any hints or ideas.
93113
(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture. (b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical induction to prove your conjecture  I understand that for part a that all multiples of 3 of n are even. So F(0),F(3),F(6)... I just don't understand how to prove it.  For part B it is the same thing except multiples of 4  Please help, thank you!
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.
27798
Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$   My (very limited) attempt so far: after creating a small list of the values $F_0=0, 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, F_{10}=55$ i can see that yes it does seem to work for instance $F_{6+3}=F_5 F_3 +F_6 F_4 = 10 +24 = 34 = F_9$. However, I really don't know where to begin as showing that this must hold in general terms. Should I be looking to use limits? Or perhaps induction? What is the best way to solve this?
34612
Numbers of ways of representing a nonnegative integer as the ordered sum of odd numbers. For the first numbers we find that:  $0 \to 0\quad \text{ways}$  $1 \to 1\quad \text{way}$  $2: (1,1) \to 1\quad \text{ways}$  $3: (1,1,1), (3) \to 2\quad \text{ways}$  $4: (1,1,1,1), (3,1), (1,3)\to 3\quad \text{ways}$  $5: (1,1,1,1,1), (3,1,1), (1,3,1), (1,1,3), (5)\to 5\quad \text{ways}$  So, if $A_n$ is the numbers of ways to represent the nonnegative integer n as the ordered sum of $n$ (nonnegative) odd numbers, then $A_n = F_n$ where $F_n$ is the Fibonacci number.  How could this be proved?   I was trying to prove this by induction, but I'm having problems with the induction step. I really don't know what to do there.
56757
Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$   So I proved the base case where $n=1$ and got $\frac{1}{2}$  Then since $n=k$ implies $n=k+1$ I setup the problem like so:  $\frac{k}{(k+1)!}+\frac{(k+1)}{(k+2)!}=1-\frac{1}{(k+2)!}$  After trying to simplify it I got the following:  $\frac{k(k+2)!+(k+1)(k+1)!}{(k+1)!(k+2)!}=1-\frac{1}{(k+2)!}$  However, I'm having trouble simplifying it to match the RHS.  Hints?
63208
This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n &gt; 1$,  where $u_0 = 0$ and $u_1 = 1$.   Show that     $$u_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$    Please help me with its proof. Thank you.
16254
I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows  Proof(By Induction)  $P(n)$:The Fibonacci numbers $F_n$ and $F_{n + 1}$ are relatively prime.  Base Case: $P(0)$ is true because $F_0 = 0$ and $F_1 = 1$ are relatively prime.  Inductive Step:   Assume $P(n)$ to be true. Now to show that for $n \geq 0$, $P(n) \implies P(n + 1)$  $\implies \gcd(F_n, F_{n + 1}) = 1$  $\implies s(F_n) + t(F_{n + 1}) = 1$  $\implies s(F_{n + 2} - F_{n + 1}) + t(F_{n + 1}) = 1$  $\implies (t - s)(F_{n + 1}) + s(F_{n + 2}) = 1$  $\implies \gcd(F_{n + 1}, F_{n + 2}) = 1$  $\implies P(n + 1)$ is true  Thus, by induction $P(n)$ is true for all $n \geq 0$.
1462
The binomial sum   $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$   satisfies the Fibonacci relation.   I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints or suggestions?
93565
Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$.  Prove by induction that for all $n&gt;0$,  $$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$  I assume $P(n)$ is true and try to show $P(n+1)$ is true, but I got stuck with the algebra. How do we reach $P(n+1)$ from $P(n)$? Also, strong induction may be used instead.
18466
Let $f_1, f_2,\dots,f_i,\dots$ be the Fibonacci sequence with $f_1=f_2=1$. For any $a,b\in\mathbb{N}$ with $a&lt;b$, suppose the Euclidean algorithm takes $n$ long divisions to compute $\gcd(a,b)$. If $a\le f_j$, then $n\le j-1$, for $j\ge2$.   I want to prove this problem. But I can't see any connection between Fibonacci and Euclidean algorithm. If anyone can give a hint about first step, it will be very thankful.  My guess is to use induction.
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?
5998
Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} &gt; \frac{13}{24}$ for $n&gt;1,n\in\Bbb N$  To solve it I used induction but it is leading me nowhere my attempt was as follows:  Lets assume the inequality is true for $n = k$ then we need to prove that it is true for $k+1$  so we need to prove $\frac1{k+2} + \frac1{k+3}+\cdots+\frac1{2(k+1)} &gt; 13/24$  I don't know where to go from here please help.
15097
Problem: Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.  My work: So I think I have to do a proof by induction and I just wanted some help editing my proof.  My attempt:  Let $P(n)=1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.  Then $$P(1)=1^2=\frac{1(1+1)(2+1)}{6}$$ $$1=\frac{6}{6}.$$ So $P(1)$ is true.  Next suppose that $P(k)=1^2+2^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}$ for $k \in \mathbb{N}$. Then adding $(k+1)^2$ to both sides of $P(k)$ we obtain the following: $$1^2+2^2+\cdots+k^2+(k+1)^2=\frac{k(k+1)(2k+1)}{6}+(k+1)^2$$ $$=\frac{2k^3+3k^2+k+6(k^2+2k+1)}{6}$$ $$=\frac{2k^3+9k^2+13k+6}{6}$$ $$=\frac{(k^2+3k+2)(2k+3)}{6}$$ $$=\frac{(k+1)(k+2)(2k+3)}{6}$$ $$=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$$ $$=P(k+1).$$ Thus $P(k)$ is true for $k \in \mathbb{N}$. Hence by mathematical induction, $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ is true for $n \in \mathbb{N}$.