Q.Prove that $2^n > n$ for all positive integers $n$.

Let $P(n)$ be the statement $2^n>n$.

Base case: For $n=1$,

so $P(1)$ is true.

Inductive step: Assume $P(k)$ is true for some $k\ge1$, i.e.

We must show $P(k+1)$ is true, i.e. $2^{k+1}>k+1$.

Multiply both sides of the induction hypothesis by $2$:

Since $k\ge1$, we have $k\ge1$, so

Combining the two inequalities:

Thus $P(k)\Rightarrow P(k+1)$.

Inequality-type induction. Multiply the induction hypothesis $2^k>k$ by $2$ to get $2^{k+1}>2k$, then use the elementary fact $2k\ge k+1$ (true for $k\ge1$) to chain the inequalities down to $k+1$.

• Trying to add $1$ to both sides of $2^k>k$ instead of multiplying by $2$ — this does not directly relate to $2^{k+1}$.
• Forgetting to justify $2k\ge k+1$ (it requires $k\ge1$, which holds since $k$ is a positive integer).
• Sloppily writing "$2^{k+1}=2k$" instead of the correct inequality "$2^{k+1}>2k$".