High School Mathematics Extensions/Mathematical Proofs/Solutions

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Mathematical proofs

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

Mathematical induction exercises

1.

Prove that 1² + 2² + ... + n² = n(n+1)(2n+1)/6

When n=1,

L.H.S. = 1² = 1

R.H.S. = 1*2*3/6 = 6/6 = 1

Therefore L.H.S. = R.H.S.

Therefore this is true when n=1.

Assume that this is true for some positive integer k,

i.e. 1² + 2² + ... + k² = k(k+1)(2k+1)/6

${\begin{matrix}1^{2}+2^{2}+3^{2}+...+k^{2}&=&{\frac {k(k+1)(2k+1)}{6}}\\1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}&=&{\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}\\\ &=&{\frac {1}{6}}(k+1)\left[k(2k+1)+6(k+1)\right]\\\ &=&{\frac {1}{6}}(k+1)\left[2k^{2}+7k+6\right]\\\ &=&{\frac {(k+1)(k+2)(2k+3)}{6}}\end{matrix}}$

Therefore this is also true for k+1.

Therefore, by the principle of mathematical induction, this holds for all positive integer n.

2.

Prove that for n ≥ 1,

$(1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}$

where x_n and y_n are integers.

When n=1,

$1+{\sqrt {5}}=x_{1}+y_{1}{\sqrt {5}}$

Therefore x₁=1 and y₁=1, which are both integers.

Therefore this is true when n=1.

Assume that this is true for some positive integer k,

i.e. $(1+{\sqrt {5}})^{k}=x_{k}+y_{k}{\sqrt {5}}$ where x_k and y_k are integers.

${\begin{matrix}(1+{\sqrt {5}})^{k}&=&x_{k}+y_{k}{\sqrt {5}}\\(1+{\sqrt {5}})^{k+1}&=&(x_{k}+y_{k}{\sqrt {5}})(1+{\sqrt {5}})\\\ &=&x_{k}+y_{k}{\sqrt {5}}+x_{k}{\sqrt {5}}+5y_{k}\\\ &=&(x_{k}+5y_{k})+(x_{k}+y_{k}){\sqrt {5}}\end{matrix}}$

Because x_k and y_k are both integers, therefore x_k + 5y_k and x_k + y_k are integers also.

Therefore this is true for k+1 also.

Therefore, by the principle of mathematical induction, this holds for all positive integer n.

3. (The solution assume knowledge in binomial expansion and summation notation)

Note that

$\sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}$

Prove that there exists an explicit formula for

$\sum _{i=1}^{n}i^{m}$ for all integer m. E.g.

$1^{3}+2^{3}+...+n^{3}={\frac {n^{2}(n+1)^{2}}{4}}$

It's clear that 1¹ + 2¹ + ... = (n+1)n/2. So the proposition is true for m=1.

Suppose that

$\sum _{i=1}^{n}i^{j}$

has an explicit formula in terms of n for all j < k (**), we aim to prove that

$\sum _{i=1}^{n}i^{k}$

also has an explicit formula.

Starting from the property given, i.e.

$\sum _{i=1}^{n}[i^{k+1}-(i-1)^{k+1}]=n^{k+1}$

$\sum _{i=1}^{n}[i^{k+1}-\sum _{j=0}^{k+1}{k+1 \choose j}i^{j}]=n^{k+1}$

$\sum _{i=1}^{n}[i^{k+1}-{k+1 \choose k+1}i^{k+1}-\sum _{j=0}^{k}{k+1 \choose j}i^{j}]=n^{k+1}$

$\sum _{i=1}^{n}[\sum _{j=0}^{k}{k+1 \choose j}i^{j}]=n^{k+1}$

$\sum _{j=0}^{k}[\sum _{i=1}^{n}{k+1 \choose j}i^{j}]=n^{k+1}$

$\sum _{j=0}^{k}[{k+1 \choose j}\sum _{i=1}^{n}i^{j}]=n^{k+1}$

Since we know the formula for power sum of any power less then k (**), we can solve the above equation and find out the formula for the k-th power directly.

Hence, by the principle of strong mathematical induction, this proposition is true.

Additional info for question 3

The method employed in question 3 to find out the general formula for power sum is called the method of difference, as shown by that we consider the sum of all difference of adjacant terms.

Aside from the method above, which lead to a recursive solution for finding the general formula, there're also other methods, such as that of using generating function. Refer to the last question in the generating function project page for detail.