Question 9 of 12

Question 9 (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) The claimed identity for all $n\ge 1$. (b) A flawed strong-induction "proof" that every power of a nonzero real is 1.

Find. (a) A rigorous proof (by induction). (b) The precise step where the argument breaks down.

Approach. (a) standard induction on $n$: verify the base case, then add the $(k+1)$-th term to the inductive hypothesis and simplify. (b) trace the inductive step for the smallest possible $k$ and check every exponent used is actually covered by the inductive hypothesis.

1. (a) Prove $1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1$ by induction on $n$. Base case ($n=1$): LHS $=1\cdot1!=1$. RHS $=(2)!-1=2-1=1$. Equal, so the base case holds. Inductive step: assume $1\cdot1!+\cdots+k\cdot k!=(k+1)!-1$ for some $k\ge 1$ (inductive hypothesis). Add the next term $(k+1)\cdot(k+1)!$ to both sides: $$1\cdot1!+\cdots+k\cdot k!+(k+1)(k+1)! = \big[(k+1)!-1\big]+(k+1)(k+1)!$$ Factor $(k+1)!$ from the right-hand side: $$=(k+1)!\big[1+(k+1)\big]-1=(k+1)!(k+2)-1=(k+2)!-1$$ This is exactly the claimed formula with $n=k+1$. By the principle of mathematical induction, the identity holds for all $n\ge 1$. $$\boxed{1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1\ \text{for all } n\ge1}$$
2. (b) Locating the flaw. The basis covers only $n=0$, so the inductive step must work from $k=0$ (using $a^0=1$ to conclude $a^1=1$). At $k=0$ the step reads $a^{1}=\dfrac{a^{0}\cdot a^{0}}{a^{-1}}$. The exponent $k-1=-1$ is NEGATIVE, so $a^{k-1}=a^{-1}$ is not covered by the inductive hypothesis (which only assumes $a^j=1$ for nonnegative $j\le k$); in fact $a^{-1}=1/a$, which equals 1 only when $a=1$. The step is valid only for $k\ge1$, but it is needed at $k=0$ to get from the basis to $a^1$, so the chain never starts and the "proof" collapses (as it must, since $a^1=a\ne1$ whenever $a\ne1$). $$\boxed{\text{Flaw: at } k=0 \text{ the step uses } a^{k-1}=a^{-1},\text{ which the hypothesis } (0\le j\le k) \text{ does not cover,}}$$ $$\boxed{\text{so the step from } a^0=1 \text{ to } a^1=1 \text{ is unjustified and the whole argument collapses.}}$$