Collection of Maths Problems

Fibonacci sequence

Task number: 3316

• Variant

  \(\displaystyle F_n\le \left(\frac{1+\sqrt{5}}{2}\right)^{n-1}\).

• Hint

  To begin the induction you must verify the statement for two values.

• Solution

  For \(n=1\):
  \(\displaystyle\left(\frac{1+\sqrt{5}}{2}\right)^0=1\ge 1= F_1\)

  For \(n=2\):
  \(\displaystyle\left(\frac{1+\sqrt{5}}{2}\right)^1\ge 1{,}6 > 1= F_2\)

  Induction step \(n-2,n-1 \to n\):
  \(\displaystyle F_n=F_{n-1}+F_{n-2}\le \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} + \left(\frac{1+\sqrt{5}}{2}\right)^{n-3}= \left(\frac{1+\sqrt{5}}{2}\right)^{n-3} \left[\frac{1+\sqrt{5}}{2}+1\right]=\\ \displaystyle =\left(\frac{1+\sqrt{5}}{2}\right)^{n-3} \left(\frac{1+\sqrt{5}}{2}\right)^2= \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \).

• Variant

  \(\displaystyle \sum_{i=1}^{n}F_i =F_{n+2}-1\).

• Hint

  Here you may begin the induction using a single value, why?

• Solution

  For \(n=1\):
  \(\displaystyle\sum_{i=1}^1 F_i = 1 = 2-1= F_3-1\).

  Induction step \(n-1 \to n\):
  \(\displaystyle\sum_{i=1}^n F_i = \left(\sum_{i=1}^{n-1} F_i\right) + F_n =F_{n+1}-1+F_n =F_{n+2}-1\).

• Variant

  \(\displaystyle\sum_{i=1}^{n}F_i^2 =F_nF_{n+1}\).

• Solution

  For \(n=1\):
  \(\displaystyle\sum_{i=1}^1 F_i^2 = 1^2 = 1{\cdot} 1= F_1 F_2\).

  Induction step \(n-1 \to n\):
  \(\displaystyle\sum_{i=1}^n F_i^2 = \left(\sum_{i=1}^{n-1} F_i^2\right) + F_n^2 =F_{n-1}F_n+F_n^2 =F_n(F_{n-1}F_n)=F_nF_{n+1}\).

• Variant

  \(\displaystyle\sum_{i=1}^{n}F_{2i-1} =F_{2n}\).

• Solution

  For \(n=1\):
  \(\displaystyle\sum_{i=1}^1 F_{2i-1} = F_1 = 1= F_2\).

  Induction step \(n-1 \to n\):
  \(\displaystyle\sum_{i=1}^n F_{2i-1} = \left(\sum_{i=1}^{n-1} F_{2i-1}\right) + F_{2n-1} =F_{2n-2}+F_{2n-1} =F_{2n}\).