Induction & Recursion · step 13 of 13

Fibonacci identities by induction

The Fibonacci numbers F₁ = F₂ = 1 and Fₙ = Fₙ₋₁ + Fₙ₋₂ generate an unusually rich family of identities, and almost all of them fall to induction. The recurrence itself is what makes the step work: when you meet Fₖ₊₂ you can always split it as Fₖ₊₁ + Fₖ, which is exactly what lets the hypothesis apply.

Practise fibonacci identities by induction free → All Induction & Recursion subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Fix the indexing conventionSome books start F₀ = 0, others F₁ = 1. Identities shift by one between conventions, so state yours.
Verify the required base casesIdentities involving two consecutive terms need two bases.
Split using the recurrence in the stepReplace Fₖ₊₂ with Fₖ₊₁ + Fₖ so the hypothesis becomes applicable.
Simplify to the target formCollect terms until the k+1 instance of the identity appears exactly.

Worked example

Prove F₁ + F₂ + … + Fₙ = Fₙ₊₂ − 1, with F₁ = F₂ = 1.

Base n = 1: LHS = 1, RHS = F₃ − 1 = 2 − 1 = 1 ✓.
Assume F₁ + … + Fₖ = Fₖ₊₂ − 1.
Then F₁ + … + Fₖ + Fₖ₊₁ = (Fₖ₊₂ − 1) + Fₖ₊₁.
= (Fₖ₊₁ + Fₖ₊₂) − 1 = Fₖ₊₃ − 1, by the recurrence.

Answer. The identity holds for all n ≥ 1 by induction, with the recurrence Fₖ₊₁ + Fₖ₊₂ = Fₖ₊₃ doing the work in the step.

Where marks get dropped

These are the specific errors that cost credit on fibonacci identities by induction questions — QED's rubric penalises each of them separately.

Mixing indexing conventions mid-proof, which shifts the identity by one and makes the base case fail.
Failing to use the recurrence in the step. Without splitting a Fibonacci term the hypothesis cannot be applied.
Checking a few numerical values instead of proving. Cassini’s identity FₙFₙ₊₂ − Fₙ₊₁² = (−1)^(n+1) alternates sign, and a small sample can look like a coincidence.

Practise this until it is automatic

Unlimited fresh questions

QED generates new fibonacci identities by induction problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Induction & Recursion mastery is tracked so you know when this is exam-ready.

Fibonacci identities by induction — frequently asked questions

What is Cassini’s identity?

Fₙ₋₁Fₙ₊₁ − Fₙ² = (−1)ⁿ. The induction step uses the recurrence once and the sign flips because the expression negates.

Is there a closed form for Fₙ?

Binet’s formula Fₙ = (φⁿ − ψⁿ)/√5 with φ = (1+√5)/2. Remarkably it always yields an integer despite the surds.

Why do so many Fibonacci identities exist?

Because the recurrence is a linear map with a matrix form: [[1,1],[1,0]]ⁿ has Fibonacci entries, so matrix identities such as determinants translate directly into Fibonacci identities.

The rest of Induction & Recursion

Mathematical, strong & structural induction; recursion. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make fibonacci identities by induction exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →