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

< High School Mathematics Extensions < Mathematical Proofs < Problem Set

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

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.

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.