# High School Mathematics Extensions/Mathematical Proofs/Problem Set/Solutions
## Mathematical Proofs Problem Set

1.
    For all
    ${\begin{matrix}a&>&0\\n+a&>&n\\n&>&n-a\\{\sqrt {n}}&>&{\sqrt {n-a}}\\1&>&{\frac {\sqrt {n-a}}{\sqrt {n}}}\\{\frac {1}{\sqrt {n-a}}}&>&{\frac {1}{\sqrt {n}}}\end{matrix}}$
    Therefore ${\frac {1}{\sqrt {1}}}$ , ${\frac {1}{\sqrt {2}}}$ , ${\frac {1}{\sqrt {3}}}$... $>{\frac {1}{\sqrt {n}}}$
    When a>b and c>d, a+c>b+d ( See also Replace it if you find a better one).
    Therefore we have:
    ${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>n\times {\frac {1}{\sqrt {n}}}$
    ${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\frac {n}{\sqrt {n}}}\times {\frac {\sqrt {n}}{\sqrt {n}}}$
    ${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\frac {n{\sqrt {n}}}{n}}$
    ${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\sqrt {n}}$
3.
    Let us call the proposition
    ${n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}$ be P(n)
    Assume this is true for some n, then
    ${n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}$
    $2\times \left\{{n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose 2}\right\}=2^{n+1}$
    $\left\{{n \choose 0}+{n \choose n}\right\}+\left\{{n \choose 0}+2{n \choose 1}+2{n \choose 2}+...+2{n \choose n-1}+{n \choose n}\right\}=2^{n+1}$
    $\left\{{n \choose 0}+{n \choose n}\right\}+\left\{{n \choose 0}+{n \choose 1}\right\}+\left\{{n \choose 1}+{n \choose 2}\right\}+\left\{{n \choose 2}+{n \choose 3}\right\}+...+\left\{{n \choose n-1}+{n \choose n}\right\}=2^{n+1}$
    Now using the identities of this function:${n \choose a}+{n \choose a+1}={n+1 \choose a+1}$(Note:If anyone find wikibooks ever mentioned this, include a link here!),we have:
    $\left\{{n \choose 0}+{n \choose n}\right\}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}=2^{n+1}$
    Since ${n \choose 0}={n \choose n}=1$ for all n,
    ${n+1 \choose 0}+{n+1 \choose n+1}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}=2^{n+1}$
    ${n+1 \choose 0}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}+{n+1 \choose n+1}=2^{n+1}$
    Therefore P(n) implies P(n+1), and by simple substitution P(0) is true.
    Therefore by the principal of mathematical induction, P(n) is true for all n.
Alternate solution Notice that
    $(a+b)^{n}={n \choose 0}a^{n}+{n \choose 1}a^{n-1}b+\cdots +{n \choose n}b^{n}$
letting a = b = 1, we get
    $(1+1)^{n}=2^{n}={n \choose 0}+{n \choose 1}+\cdots +{n \choose n}$
as required.
5.
    Let $P(x)=x^{n}+y^{n}\,$ be a polynomial with x as the variable, y and n as constants.
    ${\begin{matrix}P(-y)&=&(-y)^{n}+y^{n}\\\ &=&-y^{n}+y^{n}({\mbox{When n is an odd integer}})\\\ &=&0\end{matrix}}$
    Therefore by factor theorem(link here please), (x-(-y))=(x+y) is a factor of P(x).
    Since the other factor, which is also a polynomial, has integer value for all integer x,y and n (I've skipped the part about making sure all coeifficients are of integer value for this moment), it's now obvious that
    ${\frac {x^{n}+y^{n}}{x+y}}$ is an integer for all integer value of x,y and n when n is odd.