Tagged Questions
2
votes
2answers
37 views
proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3
I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers:
$$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
1
vote
2answers
47 views
Induction on the Fibonacci sequence?
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.
...
7
votes
2answers
72 views
Fiboncacci theorem: Proof by induction
I have the following theorem to prove by induction:
$$
F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$
It is mentioned in my script that the proof should be possible only by using the ...
2
votes
4answers
187 views
Fibonacci Induction Proof
Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step.
Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$
I ...
1
vote
4answers
127 views
Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio
I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition.
Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$.
Proof: ...
2
votes
1answer
72 views
Simple Fibonacci / Lucas Numbers Relationship
Prove the identity by induction:
$$ F_{2n} = F_n L_n, $$
where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively.
I have an answer but am not happy with it since it doesn't ...
4
votes
3answers
141 views
Why doesn't this induction “proof ”show $f_n = (\phi)^n + (1-\phi)^n$?
Here, $\phi$ is the golden ratio and $f_n$ is the $n^{th}$ Fibonacci number. The formula I'm using is actually the closed form of the Lucas numbers.
Let $n = 1$. Then $f_n = 1$ and $\phi + 1 - \phi ...
3
votes
2answers
356 views
Proof by induction for Fibonacci numbers
How can we prove by induction the following?
$
F_{n+1} = \left\{
\begin{array}{l l}
F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if $n$ is even}\\
...
1
vote
1answer
433 views
fibonacci numbers - induction proof
i am trying to prove this statement of fibonacci numbers by induction, i am stuck though on the way:
my steps:
definition:
$F_{0}:=0, F_{1}:=1 $ and $F_{n}:=F_{n-1}+F_{n-2}$
The Hypothesis is: ...
4
votes
1answer
124 views
prove that $\operatorname{fib}(n)<{(5/3)}^n$
I am trying to prove that
$$ \operatorname{fib}(n)<\left(\frac{5}{3}\right)^n $$
where $\operatorname{fib}(n)$ is the $n^{th}$ fibonacci number. For a proof I used induction, as we know
...
1
vote
2answers
411 views
Fibonacci numbers and proof by induction
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>0$,
$$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$
I assume $P(n)$ is true and try to show ...
3
votes
1answer
444 views
How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$
I am trying to prove it by induction, but I'm stuck
$$\mathrm{fib}(0) = 0 < 0! = 1;$$
$$\mathrm{fib}(1) = 1 = 1! = 1;$$
Base case n = 2,
$$\mathrm{fib}(2) = 1 < 2! = 2;$$
Inductive case ...
4
votes
3answers
337 views
Prove by induction Fibonacci equality
[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.
...
6
votes
4answers
791 views
Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]
Possible Duplicate:
Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer
This is a homework question so I'm looking to just be nudged in ...
3
votes
2answers
205 views
$f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$
I thought I had this question down, but while looking over my solution, I think I'm missing a step.
I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if ...
