How to prove by Induction on k. using Fibonacci Numbers

In summary, the conversation discusses Zeckendorf's Theorem and how any representation of the form (Zeckendorf's Theorem) implies that $F_{k_{1}} \leq n < F_{k_{1}+1}$, with a proof by induction provided. The equation is shown to hold for all $k \geq 2$.
  • #1
Spider
1
0
Please guide me how to prove the last equation by induction.
Regards!

Conversely, any representation of the form (Zeckendorf's Theorem)
$$n=F_{k_{1}}+F_{k_{2}}+...+F_{k_{r}}, \quad k_{1}\gg k_{2}\gg ... \gg k_{r} \gg 0.$$
Implies that
$$ F_{k_{1}} \leq n < F_{k_{1}+1}, $$
because the largest possible value of $F_{k_{2}}+...+F_{k_{r}},$ when $k\gg k_{2}\gg...\gg k_{r}\gg0\:$is
$$F_{k-2}+F_{k-4}+...+F_{k\,mod\,2+2}=F_{k-1}-1, \quad \quad if\: k\geq2.$$
This last equation is to prove by induction on $k;$ the left-hand side is zero when $k$ is $2$ or $3$. Therefore $k_{1}$ is the greedily chosen value described earlier, and the representation must be unique.
 
Physics news on Phys.org
  • #2
Proof by induction:Base case: When $k=2$, the equation becomes $F_{k-2}+F_{k-4}+...+F_{k\,mod\,2+2}=F_0-1=0$. Inductive step: Assume that the equation holds for some $k\geq2$. Then we have to show that it also holds for $k+1$.$F_{k+1-2}+F_{k+1-4}+...+F_{(k+1)\,mod\,2+2}$$= F_{k-1}+F_{k-3}+...+F_{(k+1)\,mod\,2+2}$ (by inductive hypothesis)$= F_{k-1}+F_{k-3}+...+F_{k+1-2}$ (since $k+1 \geq 2$)$ = F_{k-1}+F_{k-2}+F_{k-4}+...+F_{k+1-2}$ (since $k+1-2 \geq 0$)$= F_{k+1-1}-1$ (by definition of Fibonacci numbers)Therefore, the equation holds for $k+1$. By mathematical induction, the equation holds for all $k \geq 2$.
 

1. How do I begin a proof by induction on k using Fibonacci numbers?

To begin a proof by induction on k using Fibonacci numbers, you must first state the base case. This is typically when k equals 0 or 1. Then, you can assume that the statement holds for some arbitrary value of k, which is known as the induction hypothesis. Finally, you must prove that the statement holds for k+1 using the induction hypothesis and the recursive definition of Fibonacci numbers.

2. What is the formula for the nth Fibonacci number?

The formula for the nth Fibonacci number is Fn = Fn-1 + Fn-2, where F0 = 0 and F1 = 1. This means that each Fibonacci number is equal to the sum of the two previous numbers in the sequence.

3. Can I use any value of k in a proof by induction on k using Fibonacci numbers?

No, you cannot use any value of k in a proof by induction on k using Fibonacci numbers. This is because the base case and induction step must be valid for all natural numbers, not just a specific value of k. It is important to choose the base case and induction step carefully in order to prove the statement for all values of k.

4. How do I know if a statement is true for all values of k using Fibonacci numbers?

To prove that a statement is true for all values of k using Fibonacci numbers, you must show that it holds for the base case (usually k = 0 or 1) and that it holds for k+1 whenever it holds for k. This is known as the induction step. If you can successfully prove the base case and induction step, then the statement is true for all natural numbers.

5. Are there any other techniques besides induction for proving statements about Fibonacci numbers?

Yes, there are other techniques besides induction for proving statements about Fibonacci numbers. For example, you can use the Binet formula or the closed-form formula to directly calculate Fibonacci numbers. You can also use proof by contradiction or proof by counterexample to disprove a statement about Fibonacci numbers. However, induction is often the most straightforward and commonly used method for proving statements about Fibonacci numbers.

Similar threads

  • Quantum Physics
Replies
0
Views
633
Replies
6
Views
541
Replies
3
Views
445
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
913
Replies
2
Views
680
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
781
Replies
1
Views
758
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
Back
Top