数学代写|MATH3240 Number theory

Prove that for any odd number $m \geq 1$, the number 9 divides $4^m+5^m$.
Solution:
Every odd number $m$ can be written as $2 n+1$, for some $n \geq 0$ (by the division theorem the remainder when dividing by 2 is 1 or 0 , and since $m$ is odd, it must be a remainder of 1 ). We use induction on $n$ to prove the result. The base case is trivial since $4+5=9$ is divisible by 9 . Suppose next that $n \geq 1$ is a number such that $4^{2 n+1}+5^{2 n+1}$ is divisible by 9 . Let us write $4^{2 n+1}+5^{2 n+1}=9 k$ for some $k \geq 1$. We shall show that $4^{2(n+1)+1}+5^{2(n+1)+1}$ is also divisible by 9 . Indeed:
$$
\begin{aligned}
4^{2 n+3}+5^{2 n+3} & =16 \cdot 4^{2 n+1}+25 \cdot 5^{2 n+1}=16\left(4^{2 n+1}+5^{2 n+1}\right)+9 \cdot 5^{2 n+1} \
& =16 \cdot 9 k+9 \cdot 5^{2 n+1}=9\left(16 k+5^{2 n+1}\right) .
\end{aligned}
$$

Hence, $4^{2(n+1)+1}+5^{2(n+1)+1}$ is also divisible by 9 . Hence, the induction step is proven, and by the Principle of Mathematical Induction, the property is true for all numbers $n \geq 1$, and so $4^m+5^m$ is divisible by 9 for all odd numbers $m \geq 1$. Notice that this property is not true for even $m$, e.g. $4^2+5^2=16+25=\overline{4} 1$.

Prove a formula for the least number of moves required to move a Tower of Hanoi with $n$ disks to another pole.

Solution:
We shall prove using induction that the least number of moves is $2^n-1$, for all $n \geq 1$. The base case is trivial: if you only have one disk, then it only takes one move to take one disk to another pole.

Now, suppose that the least number of moves to take a tower of $n$ disks to another pole is exactly $2^n-1$. Let us suppose that we have a tower of $n+1$ disks. In order to move the tower, we will eventually have to move the last disk at the bottom of the pile. In order to access the last disk, we first need to move the $n$ disks on top to another pole. Notice that we need them all in one single pole to allow space to move the largest disk to another pole. This will take at least $2^n-1$ moves, by the induction hypothesis. Then we can move the $(n+1)$ th disk to another pole (at least 1 extra move) and, last, we need to move the other $n$ disks back on top of the largest disk. This last procedure is identical to moving a tower of $n$ disks to another pole, hence, by the induction hypothesis, it will take at least $2^n-1$ moves. In total, we have used at least the following number of moves:
$$
\left(2^n-1\right)+1+\left(2^n-1\right)=2 \cdot 2^n-1=2^{n+1}-1
$$

Hence, the induction step is proven, and by the Principle of Mathematical Induction, the property is true for all $n \geq 1$.

(a) Show that $n ! \leq n^n$ for all $n>0$.
(b) $(n+1)^{(n-1)} \leq n^n$ for all $n>0$.
Solution:
(a). For $n=1$ we have $1 !=1 \leq 1^1=1$. Now suppose that $n ! \leq n^n$. Then:
$$
(n+1) !=(n+1) \cdot n ! \leq(n+1) n^n \leq(n+1)(n+1)^n \leq(n+1)^{(n+1)},
$$
since $n<(n+1)$. Therefore, by the principle of mathematical induction, the result is true for all $n \geq 1$.

(b). Let us start with the base case $n=1: 1=2^0 \leq 1^1=1$. Now, let us assume that $(n+1)^{(n-1)} \leq n^n$ for some $n \geq 1$. Equivalently, we may assume that:
$$
\left(\frac{n+1}{n}\right)^n \leq n+1
$$
We shall prove that:
$$
\left(\frac{n+2}{n+1}\right)^{n+1} \leq ? n+2
$$
Indeed, notice that $\frac{n+2}{n+1} \leq \frac{n+1}{n}$, for all $n \geq 1$ and therefore:
$$
\begin{aligned}
\left(\frac{n+2}{n+1}\right)^{n+1} & =\left(\frac{n+2}{n+1}\right)^n \cdot\left(\frac{n+2}{n+1}\right) \leq\left(\frac{n+1}{n}\right)^n \cdot\left(\frac{n+2}{n+1}\right) \
& \leq(n+1) \cdot \frac{(n+2)}{(n+1)} \leq n+2
\end{aligned}
$$
Therefore, by the principle of mathematical induction, the result is true for all $n \geq 1$

Note: Have you noticed how HARD it is to prove, using Calculus, that the function $F(x)=(x+1)^{(x-1)}$ is less than $G(x)=x^x$ ? However, induction makes it easy!