Sq.F. Fibonacci Sequence - JulTob/Mathematics GitHub Wiki

The Fibonacci sequence $( {a_n} )$ is defined by the following recurrence relation:

  1. Base Cases:
   a_1 = 1, \quad a_2 = 1.
  1. Recursive Relation:
   a_{n+2} = a_{n+1} + a_n.

Now, let's address each part of the problem.

Part (a): Prove that $( a_{n+1} a_{n-1} = (a_n)^2 + (-1)^n )$

We will use mathematical induction to prove that

a_{n+1} a_{n-1} = (a_n)^2 + (-1)^n

holds for all $( n \geq 2 )$.

Step 1: Base Cases

  1. For $( n = 2 )$:

    • $( a_2 = 1 )$, $( a_1 = 1 )$, and $( a_3 = a_2 + a_1 = 1 + 1 = 2 )$.
    • The left side of the equation is $( a_{3} a_{1} = 2 \cdot 1 = 2 )$.
    • The right side of the equation is $( (a_2)^2 + (-1)^2 = 1^2 + 1 = 2 )$.

    So, the formula holds for $( n = 2 )$.

  2. For $( n = 3 )$:

    • $( a_3 = 2 )$, $( a_2 = 1 )$, and $( a_4 = a_3 + a_2 = 2 + 1 = 3 )$.
    • The left side of the equation is $( a_{4} a_{2} = 3 \cdot 1 = 3 )$.
    • The right side of the equation is $( (a_3)^2 + (-1)^3 = 2^2 - 1 = 4 - 1 = 3 )$.

    So, the formula holds for $( n = 3 )$.

Therefore, the base cases are true for $( n = 2 )$ and $( n = 3 )$.

Step 2: Inductive Hypothesis

Assume that the formula holds for $( n = k )$; that is, assume:

a_{k+1} a_{k-1} = (a_k)^2 + (-1)^k.

Step 3: Inductive Step

We need to prove that if the formula holds for $( n = k )$, then it also holds for $( n = k + 1 )$. In other words, we need to show:

a_{k+2} a_k = (a_{k+1})^2 + (-1)^{k+1}.

Proof of the Inductive Step

Using the recurrence relation $( a_{k+2} = a_{k+1} + a_k )$, we have:

a_{k+2} a_k = (a_{k+1} + a_k) a_k = a_{k+1} a_k + (a_k)^2.

By the inductive hypothesis, we know that:

a_{k+1} a_{k-1} = (a_k)^2 + (-1)^k.