# High School Mathematics Extensions/Mathematical Proofs/Solutions
## 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$ + 2$^2$ + ... + n$^2$ = n(n+1)(2n+1)/6
       When n=1,
       L.H.S. = 1$^2$ = 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$ + 2$^2$ + ... + k$^2$ = 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$=1 and y$_1$=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$^1$ + 2$^1$ + ... = (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 than 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.