Problems

Filters
Clear Filters

1 problem found

2015 Paper 1 Q8
D: 1484.0 B: 1516.0
proof by induction divisibility summation binomial theorem odd powers symmetric functions pairing argument

Show that:

  1. \(1+2+3+ \cdots + n = \frac12 n(n+1)\);
  2. if \(N\) is a positive integer, \(m\) is a non-negative integer and \(k\) is a positive odd integer, then \((N-m)^k +m^k\) is divisible by \(N\).
Let \(S = 1^k+2^k+3^k + \cdots + n^k\), where \(k\) is a positive odd integer. Show that if \(n\) is odd then \(S\) is divisible by \(n\) and that if \(n\) is even then \(S\) is divisible by \(\frac12 n\). Show further that \(S\) is divisible by \(1+2+3+\cdots +n\).

Solution:

  1. \(\,\) \begin{align*} && S & = 1 +\quad 2\quad \;\;+ \quad 3 \quad+ \cdots + \quad n \\ && S &= n + (n-1) + (n-2) + \cdots + 1 \\ && 2S &= (n+1) + (n+1) + \cdots + (n+1) \\ \Rightarrow && S &= \frac12n(n+1) \end{align*}
  2. \(\,\) \begin{align*} && (N-m)^{k} + m^k&= \sum_{i=0}^k \binom{k}{i} N^{k-i} (-m)^{i} + m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i -m^k+m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i \end{align*} which is clearly divisible by \(N\).
\begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=0}^n (\underbrace{(n-i)^k + i^k}_{\text{divisible by }n}) \\ \end{align*} Therefore \(2S\) is divisible by \(n\) and so if \(n\) is odd, \(n\) divides \(S\) and if \(n\) is even, \(\frac{n}{2}\) divides \(S\). Also notice \begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=1}^{n} (\underbrace{(n+1-i)^k + i^k}_{\text{divisible by }n+1}) \\ \end{align*} Therefore if \(n+1\) is odd, \(n+1 \mid S\) otherwise \(\frac{n+1}{2} \mid S\), and in either case \(\frac{n(n+1)}{2} \mid S\) (since they are both coprime) but this is the same as \(1 + 2 + \cdots + n \mid S\)

View