View source for HSE PS Mathematical proofs

{{High School Mathematics Extensions/TOC}}

==Mathematical Proofs Problem Set==
1.
:For all
:<math>
\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}
</math>
:Therefore <math>\frac{1}{\sqrt{1}}</math> , <math>\frac{1}{\sqrt{2}}</math> , <math>\frac{1}{\sqrt{3}}</math>... <math> > \frac{1}{\sqrt{n}}</math>
:When a>b and c>d, a+c>b+d ( [[Algebra/Solving_linear_inequalities#Properties|See also]] Replace it if you find a better one).
:Therefore we have:
:<math>\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}......+\frac{1}{\sqrt{n}}>n\times\frac{1}{\sqrt{n}}</math>
:<math>\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}}</math>
:<math>\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}......+\frac{1}{\sqrt{n}}>\frac{n\sqrt{n}}{n}</math>
:<math>\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}......+\frac{1}{\sqrt{n}}>\sqrt{n}</math>


3.
:Let us call the proposition
:<math>{n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n} = 2^n</math> be P(n)
:Assume this is true for some n, then
:<math>{n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n} = 2^n</math>
:<math>2\times \left \{ {n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose 2} \right \} = 2^{n+1}</math>
:<math>\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}</math>
:<math>\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}</math>
:Now using the identities of this function:<math>{n \choose a} + {n \choose a+1} = {n+1 \choose a+1}</math>(Note:If anyone find wikibooks ever mentioned this,include a link here!),we have:
:<math>\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}</math>
:Since <math>{n \choose 0} = {n \choose n} = 1</math> for all n,
:<math>{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}</math>
:<math>{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}</math>
: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'''<br/>
Notice that
:<math>(a + b)^n = {n \choose 0} a^n + {n \choose 1} a^{n-1}b + \cdots + {n \choose n} b^n</math>
letting ''a'' = ''b'' = 1, we get
:<math>(1 + 1)^n = 2^n = {n\choose 0} + {n \choose 1} + \cdots + {n\choose n}</math>
as required.



5.
:Let <math>P(x)=x^n + y^n\,</math> be a polynomial with x as the variable, y and n as constants.
:<math>
\begin{matrix}
P(-y) & = & (-y)^n + y^n\\
\ & = & -y^n + y^n(\mbox{When n is an odd integer})\\
\ & = & 0
\end{matrix}
</math>
: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
:<math>\frac{x^n+y^n}{x+y}</math> is an integer for all integer value of x,y and n when n is odd.