Question 2 of 12

Question 2

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) An n-fold nested sum where each index sᵢ ranges over {0,1}, with summand $1/(1^{s_1}2^{s_2}\cdots n^{s_n})$. (b) The arithmetic series of even integers $0,2,4,\ldots,2n$.

Find. Prove each closed-form identity, e.g. by induction on n.

Approach. For (a), recognize the 2ⁿ terms of the nested sum as exactly the expansion of a product of n independent binomial factors and telescope; for (b), use standard induction or the Gauss pairing trick, and verify both by direct computation for small n.

1. Part (a) — factor the nested sum into a product. Each $s_k\in\{0,1\}$ is chosen independently, so summing over all $2^n$ combinations of $(s_1,\ldots,s_n)$ is the same as distributing a product of n two-term factors, one per index: $$\sum_{s_1=0}^{1}\cdots\sum_{s_n=0}^{1}\prod_{k=1}^{n}\frac{1}{k^{s_k}} =\prod_{k=1}^{n}\left(\sum_{s_k=0}^{1}\frac{1}{k^{s_k}}\right) =\prod_{k=1}^{n}\left(1+\frac1k\right)=\prod_{k=1}^{n}\frac{k+1}{k}.$$ This is a telescoping product: numerator $k+1$ of each factor cancels the denominator $k+1$ appearing in the next factor's denominator slot, leaving only the first denominator and the last numerator: $$\prod_{k=1}^{n}\frac{k+1}{k}=\frac{2}{1}\cdot\frac{3}{2}\cdot\frac{4}{3}\cdots\frac{n+1}{n} =\boxed{n+1}.$$ Induction alternative: base case $n=1$ gives $1+1=2=1+1$; if the product up to $n-1$ equals $n$, multiplying by the next factor $(n+1)/n$ gives $n\cdot\frac{n+1}{n}=n+1$, closing the inductive step.
2. Part (b) — sum of the first (n+1) even numbers. $$\sum_{i=0}^{n}2i = 2\sum_{i=0}^{n}i = 2\cdot\frac{n(n+1)}{2}=\boxed{n(n+1)}$$ using the Gauss triangular-number identity $\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}$. By induction: base case $n=0$ gives sum $=0=0\cdot1$; assuming the sum to $2n$ is $n(n+1)$, adding the next even term $2(n+1)$ gives $n(n+1)+2(n+1)=(n+1)(n+2)$, matching the formula at $n+1$.