The Fibonacci sequence, (fn) n∈N, is defined recursively as follows:
f0 = f1 = 1,
fn = fn-2 + fn-1 (n ≥ 2)
Demonstrate for all n ∈ N:
If n ≥ 1, then fn-1 ⋅fn + 1 = f ^ 2n - (- 1) ^ n
.
To prove this equation for all n ∈ N, we can use mathematical induction.
Base case:
Let's start with n = 1:
f0 = 1
f1 = 1
Now let's substitute these values into the equation:
f0 ⋅ f1 + 1 = 1 ⋅ 1 + 1 = 2
f2 = 1
Also, let's calculate f^2n - (-1)^n:
f^2(1) - (-1)^1 = f(2) + 1 = 1 + 1 = 2
Therefore, the equation holds true for the base case.
Inductive step:
Assume that for some k ≥ 1, the equation holds true:
fk-1 ⋅ fk + 1 = f^2k - (-1)^k
Now, we need to prove it holds for k + 1 as well:
fk ⋅ fk+1 + 1 = f^2(k+1) - (-1)^(k+1)
Using the definition of the Fibonacci sequence, we can rewrite the left side of the equation:
(fk-1 + fk) ⋅ fk + 1 + 1 = (fk-1 ⋅ fk + fk ⋅ fk+1 + fk + 1) + 1 = [(fk-1 ⋅ fk + 1) + (fk ⋅ fk+1 + fk + 1)] + 1
Now, let's substitute the induction hypothesis and simplify the expression:
[f^2k - (-1)^k + (fk ⋅ fk+1 + fk + 1)] + 1 = [(f^2k + fk ⋅ fk+1) + fk + 1 - (-1)^k] + 1
Next, we'll focus on the term in brackets ([(f^2k + fk ⋅ fk+1) + fk + 1 - (-1)^k]):
(f^2k + fk ⋅ fk+1) + fk + 1 - (-1)^k = f^2k + fk ⋅ fk+1 + fk + 1 + (-1)^k
We know from the Fibonacci sequence definition that f^2k = f2k - (-1)^k. Therefore, we can substitute this into the equation:
(f2k - (-1)^k + fk ⋅ fk+1) + fk + 1 + (-1)^k = f2k + fk ⋅ fk+1 + fk + 1
This can be further simplified:
f2k + fk ⋅ fk+1 + fk + 1 = fk+1 ⋅ (fk + fk+1) + (fk + fk+1)
Using the property of Fibonacci numbers (fn = fn-1 + fn-2), we can replace fk+1 with fk + fk-1:
(fk + fk-1) ⋅ (fk + 2fk-1) + (fk + 2fk-1)
Now let's simplify the expression even further:
(fk + fk-1) ⋅ (fk + 2fk-1) + (fk + 2fk-1) = [fk + fk-1 + (fk + 2fk-1)] ⋅ (fk + 2fk-1)
Simplifying the expression in brackets:
[fk + fk-1 + (fk + 2fk-1)] ⋅ (fk + 2fk-1) = (2fk + 3fk-1) ⋅ (fk + 2fk-1)
Expanding the two terms:
(2fk + 3fk-1) ⋅ (fk + 2fk-1) = 2fk ⋅ fk + 2fk ⋅ 2fk-1 + 3fk-1 ⋅ fk + 3fk-1 ⋅ 2fk-1
Combining similar terms:
2fk ⋅ fk + 4fk ⋅ fk-1 + 3fk-1 ⋅ fk + 6fk-1 ⋅ fk-1
Now, notice that the first term (2fk ⋅ fk) is equal to fk+1 ⋅ fk (using the definition of the Fibonacci sequence fn = fn-1 + fn-2). Similarly, the second term (4fk ⋅ fk-1) is equal to fk+1 ⋅ fk-1. We can simplify the expression further:
fk+1 ⋅ fk + fk+1 ⋅ fk-1 + 3fk-1 ⋅ fk + 6fk-1 ⋅ fk-1 = fk+1 ⋅ (fk + fk-1) + fk-1 ⋅ (3fk + 6fk-1)
Again, using the Fibonacci property (fn = fn-1 + fn-2):
fk+1 ⋅ (fk + fk-1) + fk-1 ⋅ (3fk + 6fk-1) = fk+1 ⋅ fk+1 + fk-1 ⋅ (4fk + 5fk-1)
Notice that (4fk + 5fk-1) is equal to fk+2 (using the Fibonacci property). Therefore:
fk+1 ⋅ fk+1 + fk-1 ⋅ (4fk + 5fk-1) = fk+1 ⋅ fk+1 + fk-1 ⋅ fk+2
Finally, we have:
fk+1 ⋅ fk+1 + fk-1 ⋅ fk+2 = f^2(k+1) - (-1)^(k+1)
Which is exactly what we needed to prove for the inductive step.
Conclusion:
By proving the base case and demonstrating that if the equation holds for any k ≥ 1, it also holds for k + 1, we have proven the equation for all n ∈ N. Therefore, if n ≥ 1, then fn-1 ⋅ fn + 1 = f^2n - (-1)^n.