Q.Show that $9^{n+1} - 8n - 9$ is divisible by 64, whenever $n$ is a positive integer.

Proof by Induction: From Dominoes to Certainty

Imagine you have an infinite line of dominoes standing upright. You want to be absolutely sure that every single domino will fall. How would you prove it?

You'd need two things:

1. The first domino falls — you push it.
2. If any domino falls, the next one falls too — they are close enough to knock each other over.

That's it. If both conditions hold, you know — without checking each domino individually — that every domino will eventually fall. This is the core intuition behind proof by induction.

The Problem Induction Solves

Many mathematical statements involve natural numbers ($1, 2, 3, \dots$) and claim something is true for all of them. For example:

The sum of the first $n$ odd numbers equals $n^2$.

You could check: $1 = 1^2$, $1+3 = 2^2$, $1+3+5 = 3^2$, $1+3+5+7 = 4^2$... but you can never check infinitely many cases. Induction gives you a way to prove it in just two steps.

The Precise Structure

Let $P(n)$ be a statement about a natural number $n$ (like "the sum of the first $n$ odd numbers is $n^2$"). To prove $P(n)$ is true for all $n \geq 1$, you need:

The two parts have names:

1. Base case: Prove $P(1)$ is true. (The first domino falls.)
2. Inductive step: Assume $P(k)$ is true for some arbitrary $k \geq 1$, and prove $P(k+1)$ follows. (If domino $k$ falls, domino $k+1$ falls too.)

The assumption "$P(k)$ is true" is called the inductive hypothesis.

A Worked Example

Let's prove: $1 + 3 + 5 + \dots + (2n-1) = n^2$ for all $n \geq 1$.

Base case ($n=1$):

Left side: $1$

Right side: $1^2 = 1$

So $P(1)$ is true.

Inductive step:

Assume $P(k)$ is true for some $k \geq 1$:

We want to prove $P(k+1)$:

Start from the left side of $P(k+1)$:

Replace the bracketed sum using the inductive hypothesis:

Simplify:

That's exactly the right side of $P(k+1)$. So $P(k) \implies P(k+1)$ is proved.

Since both conditions hold, $P(n)$ is true for all $n \geq 1$.

Why It Works (The Logic)

Induction is a domino chain of implications:

• $P(1)$ is true (base).
• $P(1) \implies P(2)$ (inductive step with $k=1$), so $P(2)$ is true.
• $P(2) \implies P(3)$ (inductive step with $k=2$), so $P(3)$ is true.
• $P(3) \implies P(4)$, so $P(4)$ is true.
• ... and so on, forever.

You never need to check infinitely many cases. The inductive step acts as a "machine" that, given any true $P(k)$, produces $P(k+1)$. The base case feeds the machine the first truth, and the machine keeps running forever. …