04-BS-16, December 2014, Q4 | Nivaar Exam Prep

Question 4

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 closed form $\sum_{i=1}^n i\cdot 2^i = 2+(n-1)2^{n+1}$. (b) The open statement $S(n):\ \sum_{i=1}^n i = \dfrac{(n+\frac12)^2}{2}$.

Find. (a) A full induction proof. (b1) The inductive-step implication $S(k)\Rightarrow S(k+1)$. (b2) Whether $S(n)$ is true for every positive integer.

Approach. Standard weak induction for (a): verify the base case, then show the step preserves the claim. For (b), verify the step algebraically first (it will hold identically), then separately check the base case $n=1$ — a failed base case with a valid step means the statement is never actually true, which is the point of this exercise.

a) Base case $n=1$. LHS $=1\cdot 2^1=2$. RHS $=2+(1-1)2^{2}=2+0=2$. Equal, so the base case holds.
a) Inductive step. Assume $\sum_{i=1}^{k} i\cdot 2^i = 2+(k-1)2^{k+1}$ for some $k\ge1$. Then $$\sum_{i=1}^{k+1} i\cdot2^i = \Big[2+(k-1)2^{k+1}\Big] + (k+1)2^{k+1} = 2 + 2^{k+1}\big[(k-1)+(k+1)\big] = 2+2^{k+1}(2k)$$ $$=2+k\cdot2^{k+2}=2+\big((k+1)-1\big)2^{(k+1)+1}$$ which is exactly the claimed formula at $n=k+1$. $\boxed{\sum_{i=1}^{n} i\cdot 2^i = 2+(n-1)2^{n+1}\ \text{holds for all } n\ge1 \text{ by induction}}$.
b1) Inductive step for $S(n)$. Assume $S(k)$: $\sum_{i=1}^{k} i = \frac{(k+\frac12)^2}{2}$. Adding $(k+1)$ to both sides: $$\sum_{i=1}^{k+1} i = \frac{(k+\tfrac12)^2}{2}+(k+1)=\frac{(k+\tfrac12)^2+2(k+1)}{2}=\frac{k^2+3k+\tfrac94}{2}$$ and expanding the claimed RHS at $n=k+1$: $\frac{\big((k+1)+\frac12\big)^2}{2}=\frac{(k+\frac32)^2}{2}=\frac{k^2+3k+\tfrac94}{2}$ — identical. $\boxed{S(k)\Rightarrow S(k+1)\text{ for every } k\in Z^+}$ (the step is an algebraic identity, true unconditionally).
b2) Check the base case $n=1$. $\sum_{i=1}^1 i = 1$, while the claimed formula gives $\frac{(1+\frac12)^2}{2}=\frac{(3/2)^2}{2}=\frac{9/4}{2}=\frac98=1.125$. These are NOT equal, so $S(1)$ is false. Since the true value $\frac{n(n+1)}{2}$ and the claimed $\frac{(n+1/2)^2}{2}$ differ by a constant $\frac{1}{8}$ for every $n$ (expand: $\frac{(n+\frac12)^2}{2}-\frac{n(n+1)}{2}=\frac{n^2+n+\frac14-n^2-n}{2}=\frac18$), $S(n)$ is false for every $n$, not just $n=1$. $\boxed{S(n)\text{ is FALSE for all } n\in Z^+,\text{ even though the inductive step alone is valid}}$.

Question 4 results
Part	Result
a	Identity proven true for all $n\ge1$ by induction
b1	Step $S(k)\Rightarrow S(k+1)$ holds (algebraic identity)
b2	$S(n)$ is false for every $n$ — base case fails ($1\ne 9/8$), off by constant $1/8$

Topic: Mathematical induction — proof technique and its failure modes.

Key relations: Induction requires BOTH a true base case AND a valid step; $\sum_{i=1}^n i=\frac{n(n+1)}{2}$ is the correct closed form, which $S(n)$'s formula misses by a constant $\frac18$ for every $n$.

Why this works: Part (b) is a designed illustration that a valid inductive step proves nothing on its own — it only propagates truth forward from whatever base case is supplied, and here that base case is false, so the whole chain of implications is vacuous for establishing $S(n)$.

Common pitfall: Concluding "$S(n)$ is true for all $n$" from a correct step alone without ever checking $n=1$ — this is the single most common induction error and part (b) is written specifically to test for it.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 5.1 (Mathematical Induction).

Question 4 of 12

Question 4