04-BS-16 · December 2013

Question 3 of 12: Induction and Pigeonhole Proofs

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 3: Induction and Pigeonhole Proofs (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.

Approach. Part (a) is weak induction on $n$, using the recursive definition $H_{n+1}=H_n+\frac1{n+1}$. Part (b) is the pigeonhole principle: partition $\{1,\dots,99\}$ into 9 "buckets" on which $\sqrt{\cdot}$ varies by less than 1, so 10 chosen integers force two into the same bucket.

(a) Base case $n=1$. LHS $=H_1=1$. RHS $=(1+1)H_1-1=2(1)-1=1$. Equal, base case holds.
(a) Inductive step. Assume $\sum_{i=1}^k H_i=(k+1)H_k-k$ (hypothesis). Then $$\sum_{i=1}^{k+1}H_i = \Big[\sum_{i=1}^kH_i\Big]+H_{k+1} = (k+1)H_k-k+H_{k+1}.$$ Using $H_k=H_{k+1}-\frac1{k+1}$: $$=(k+1)\Big(H_{k+1}-\frac1{k+1}\Big)-k+H_{k+1} = (k+1)H_{k+1}-1-k+H_{k+1} = (k+2)H_{k+1}-(k+1).$$ This matches the claimed formula at $n=k+1$: $\boxed{\sum_{i=1}^nH_i=(n+1)H_n-n\ \text{for all }n\ge1}$, by the principle of mathematical induction.
(b) Partition $\{1,\dots,99\}$ by $\lfloor\sqrt n\rfloor$. For $k=1,\dots,9$, let bucket $k=\{n: k^2\le n\le(k+1)^2-1\}$ (i.e. $\lfloor\sqrt n\rfloor=k$). These 9 buckets are: $[1,3],[4,8],[9,15],[16,24],[25,35],[36,48],[49,63],[64,80],[81,99]$ — together covering all of $\{1,\dots,99\}$ (sizes $3,5,7,9,11,13,15,17,19$, summing to $99$).
(b) Apply pigeonhole. 10 integers are chosen and there are only 9 buckets, so by the pigeonhole principle two of the chosen integers, $x$ and $y$, land in the SAME bucket $k$, meaning $k\le\sqrt x,\sqrt y<k+1$. Both square roots lie in an interval of length $1$, so $$\boxed{|\sqrt x-\sqrt y|<1.}$$

Final results — Question 3
Part	Result
(a)	Proved by induction: $(k+1)H_k-k+H_{k+1}=(k+2)H_{k+1}-(k+1)$
(b)	9 buckets $[k^2,(k+1)^2-1]$, $k=1..9$, cover $\{1,..,99\}$; 10 picks force 2 in one bucket $\Rightarrow\|\sqrt x-\sqrt y\|<1$

Topic: Induction with a recursively-defined summand; pigeonhole via a square-root-interval partition.

Key relations: $H_{n+1}=H_n+\frac1{n+1}$; pigeonhole: $N$ objects into $k<N$ boxes forces some box with $\ge2$ objects.

Why this works: The bucket boundaries $k^2,(k+1)^2-1$ are exactly the integers whose floor square root equals $k$, so within one bucket $\sqrt{\cdot}$ never varies by a full unit — that is the entire content of the pigeonhole argument. Nine buckets exactly cover $1..99$ because $9^2=81\le99<100=10^2$.

Common pitfall: Substituting $H_{k+1}=H_k+\frac1{k+1}$ backwards (sign error) in the induction algebra; miscounting the buckets — $\lfloor\sqrt{99}\rfloor=9$, so there are exactly 9 buckets (the last is $[81,99]$, and $10^2=100$ lies outside the set); 10 buckets would defeat the pigeonhole argument.

Source: Rosen, Discrete Mathematics and Its Applications, §5.1 (induction), §6.2 (the pigeonhole principle).

← Question 2 Next: Question 4 →