### Telescoping Series

Find $S_r = 1^r + 2^r + 3^r + ... + n^r$ where r is any fixed positive integer in terms of $S_1, S_2, ... S_{r-1}$.

### Growing

Which is larger: (a) 1.000001^{1000000} or 2? (b) 100^{300} or 300! (i.e.factorial 300)

### Climbing Powers

$2\wedge 3\wedge 4$ could be $(2^3)^4$ or $2^{(3^4)}$. Does it make any difference? For both definitions, which is bigger: $r\wedge r\wedge r\wedge r\dots$ where the powers of $r$ go on for ever, or $(r^r)^r$, where $r$ is $\sqrt{2}$?

# Tens

##### Stage: 5 Challenge Level:

We got some lovely solutions to and thoughts on this problem at various levels.

One of our younger users, Molshree from Acland Burley school, worked on a related problem by finding out when solutions could be found when the operation of 'power' in the problem was replaced by the operation of 'times'. Another younger student, Rohan from Firs Primary also worked on a related problem in which he found numbers adding to 10.

Daniel, from Savile Park Primary sent in a delightful solution in which he constructed a table of the units digit in each case, from which he proved all of the results. He writes:

Writing powers in mod 10 (units digits)

 $n$ $9^n$ $1^n$ $7^n$ $3^n$ $8^n$ $2^n$ $6^n$ $4^n$ 1 9 1 7 3 8 2 6 4 2 1 1 9 9 4 4 6 6 3 9 1 3 7 2 8 6 4 4 1 1 1 1 6 6 6 6 5 9 1 7 3 8 2 6 4

and so on -- the table repeats every 4 rows.

1) $9^{2m+1}+1^{2m+1}(\mbox{mod } 10)=9+1=10$ so must be a multiple of $10$ $7^{2m+1}+3^{2m+1}(\mbox{mod }10)=7+3$ or $3+7=10$ so must be a multiple of $10$

3) $9^{2m}-1^{2m}(\mbox{mod }10)=1-1=0$ so must be a multiple of $10$

$7^{2m}-3^{2m}(\mbox{mod }10)=1-1$ or 9-9=0 so must be a multiple of 10

2) $8^{2m}-2^{2m}(\mbox{mod }10)=4-4$ or $6-6=0$ so must be a multiple of $10$

$6^{2m}-4^{2m}(\mbox{mod }10)=6-6=0$ so must be a multiple of 10

4) $8^{2m+1}+2^{2m+1}(\mbox{mod }10)=8+2$ or $2+8=10$ so must be a multiple of $10$

$6^{2m+1}+4^{2m+1}(\mbox{mod }10)=6+4=10$ so must be a multiple of $10$.

So all are multiples of $10$.

Mark (no school given) wrote up a lovely solution using two methods: first he looked at the properties of the units digit in the sums and then looked at the implications of the binomial theorem. His solution was beautifully written up in Word, so we attach a full pdf version of his work. It is well worth a read!

Babu (no school given) proved the first part using the binomial theorem:

Consider the power $n$ as an odd number, say $2m+1$, so that we need to prove that $7^{2m+1} + 3^{2m+1}$ is a multiple of $10$ always.

$$7^{2m+1} + 3^{2m+1}= (10 - 3)^{2m+1} + 3^{2m+1}$$
On expanding the right hand side of the above equation using binomial theorem we get,
$$10^{2m+1} + _{2m+1}C_1 \times 10^{2m} \times (-3)^1 + _{2m+1}C_2 \times 10^{2m+1} \times (-3)^2+ \cdots +(-3)^{2m+1} + 3^{2m+1}$$
By cancelling the last two terms, we see that all remaining terms have a factor of $10$. Hence the sum is also a multiple of $10$.

By trial and error we can see that the result is not necessarily true for even powers.

Patrick Stevens from Woodbridge school and Robert from The King's School, Grantham both gave the clear proofs starting directly from the moular form of the equations.

For part 1, Robert wrote:

Let $n=2x+1$, where $x\in\mathbb{Z}$ Then $$\begin{eqnarray} 9^n+1^n &=& 9^{2x+1}+1^{2x+1}\cr &=& (9^2)^x\times 9 +1 \cr 9&\equiv& 9\pmod{10}\cr 9^2&\equiv& 81\pmod{10}\equiv 1\pmod{10} \end{eqnarray}$$ $$\begin{eqnarray} \therefore 9^n+1^n&\equiv&\left(1\pmod{10}\right)^x\times 9\pmod{10}+1\pmod{10}\cr &\equiv& \left(1\times 9 +1\right)\pmod{10}\cr &\equiv& 10 \pmod{10} \cr &\equiv& 0\pmod{10}\quad\quad\mbox{QED} \end{eqnarray}$$

Robert then proceeded to prove the other three parts in this way

Patrick constructed some great modular arithmetic answers. For part 2, for example, he wrote:

$8^{n}\equiv (-2)^n\pmod{10}$ so $8^n-2^n\equiv (-2)^n -2^n\pmod{10}$. Since for even $n$ we have $(-2)^n = (2)^n\pmod{10}$ we have $(-2)^n-2^n \equiv 0 \pmod{10}$; this, therefore, is divisible by $10$.

We liked this approach of Patrick's because from this it is easy to spot generalisations, along with the algebra that backs them up. Patrick continued by saying:

Let us take $x = 0$ to $9$, without losing generality, since any natural number is congruent to one of these numbers in modulo $10$. Therefore, generalising the first equation we get
$$x^n + (10-x)^n (\mbox{mod } 10) \equiv x^n + (-x)^n\equiv x^n(1 + (-1)^n)$$
Therefore, if $n$ is odd, then we have $x^n(1-1) = 0$, for all $x$.

We are now left to find a general equation for even $n$. If $n$ is even, we have $x^n(1+1) = x^n \times 2$. We have only $x = 0, 2, 4, 6, 8$ to worry about here; for $x = 0$, the product will be $0$ so this is divisible by $10$. Since we have defined $n$ to be even, then $2^n \equiv (-2)^n$, so in modulo $10$, the result will be the same for $2$ and $8$, and for $4$ and $6$. We have two cases left to check, then: $x = 2$ and $x = 4 = 2^2$. Let $x = 2$, then we have $2^n \times 2 = 2^{n+1}$; for $x = 4$, we have $(2^2)^n \times 2 \equiv 2^{2n+1}$. Neither of these will ever be divisible by $10$, since in order to have $10$ as a factor, the number must have a factor of $5$; but it has just been proved that these numbers will only be divisible by $2$. Therefore, $x^n + (10-x)^n$ is always divisible by $10$, except when $n = -2, 2, -4, 4$ in modulo $10$.

Generalising the second equation,
$$x^n - (10-x)^n (\mbox{mod }10) \equiv x^n - (-x)^n(\mbox{mod }10)$$
For all even $n$, $(-x)^n = x^n$, so $x^n - (-x)^n = x^n - x^n = 0 (\mbox{ mod} 10)$. For odd $n$, we have $x^n + x^n = 2\times x^n$; this therefore looks like it can't be generalised.

There are at least three methods of proving the results that for odd values of $n$, $9^n + 1^n$, $8^n + 2^n$, $7^n + 3^n$ and $6^n + 4^n$ are multiples of $10$ whereas, if $n$ is even, then $9^n - 1^n$, $8^n - 2^n$, $7^n - 3^n$ and $6^n - 4^n$ are multiples of $10$.

These results can be proved using the axiom of mathematical induction but a simpler approach is to use the periodicity of the values of the last digit for powers of integers. Emma from St Paul's Girls' School and Andrei from Tudor Vianu National College, Bucharest, Romania both used this method of solution. As Andrei tabulated his results his solution is shorter:

Proof using the periodicity of last digits of powers of integers and Modular arithmetic

I shall determine the last digit of each of the numbers: $1^n$, $2^n$, $3^n$, $4^n$, $6^n$, $7^n$, $8^n$, $9^n$. The last digit of $1^n$ is always 1, and for $6^n$ it is always $6$. For $2$, $3$, $7$ and $8$ the last digit of their powers repeats with periodicity $4$, as shown in the table:

 $n \pmod 4$ $0$ $1$ $2$ $3$ $2$ $6$ $2$ $4$ $8$ $3$ $1$ $3$ $9$ $7$ $7$ $1$ $7$ $9$ $3$ $8$ $6$ $8$ $4$ $2$

For $4$ and $9$, the last digit of their powers repeats with periodicity $2$:

 $n \pmod 2$ $0$ $1$ $4$ $6$ $4$ $9$ $1$ $9$
Having creating these tables, I shall prove the required results:

(1) If $n$ is odd, the last digit of $9^n$ is 9, and as the last digit of $1^n$ is always $1$, so the the last digit of $9^n + 1^n$ is $0$, and the number is a multiple of $10$.

For $7^n + 3^n$ there are two possible cases: $n = 1\pmod{4}$.

Here $7^n + 3^n = (7 + 3)\pmod{10}= 0\pmod{10}$ $n = 3\pmod{4}$. Here $7^n + 3^n = (3 + 7)\pmod{10} = 0\pmod{10}$

(2) If $n$ is even it is very easy to look in the table above to obtain the desired results.

First I look at $8^n - 2^n$ for different values of $n$ - even. If $n = 2\pmod{4}$, then $8^n - 2^n = (4-4) \pmod{10} = 0\pmod{10}$.

If $n = 0\pmod{4}$, $8^n - 2^n = (6-6) \pmod{10} = 0 \pmod {10}$.

For, $6^n - 4^n$, I also obtain $(6-6) \pmod{10} = 0 \pmod{10}$.

(3) If $n$ is even: $9^n - 1^n$ is a multiple of $10$. The proof derives evidently from the table. In a similar manner, $7^n - 3^n$ is also a multiple of $10$.

(4) If $n$ odd: $8^n + 2^n$ and $6^n + 4^n$ are both multiples of $10$.

Sam from SAC (Malta) made a very clear conjecture related to this problem:

I noticed that both $9 + 1$ and $7 + 3$ add up to $10$, so a conjecture for odd numbers is:

$(a + b)$ is a factor of $(a^n + b^n)$
where $a$ and $b$ are any constants and $n \in \{\mbox{odd numbers}\}$.

Furthermore, both $8+2$ and $6+4$ add up to $10$, so a conjecture for even numbers is

$(a + b)$ is a factor of $(a^n- b^n)$, where $a$ and $b$ are any constants and $n \in\{\mbox{even numbers}\}$

Note here that both {odd numbers} and {even numbers} are subsets of $\mathbb{N}$. Combining these conjectures I got: $(a + b)$ is a factor of $(a^n + (-1)^{n-1} b^n)$, where $a$ and $b$ are any constants and $n \in \mathbb{N}$.

Sam managed to prove this by induction

Let
$$\begin{eqnarray} f(k)&=&a^k + (-1)^{k-1} b^k\cr f(k+1)&=&a^{k+1} + (-1)^k b^{k+1} \end{eqnarray}$$
$f(k+1)$
can also be expressed as
$$\begin{eqnarray} f(k+1)&=&a^{k+1}+(-1)^{k-1} ab^k - (-1)^{k-1} ab^k+ (-1)^k b^{k+1}\cr &=&a(a^k+ (-1)^{k-1} b^k )- (-1)^{k-1} b^k (a-(-1)b)\cr &=&af(k)+ (-b)^k (a+b) \end{eqnarray}$$
Therefore, $(a + b)$ is a factor of $f(k + 1)$ if it is a factor of $f(k)$. Using $k = 1: f(1)= a+b$ Therefore, $(a + b)$ is a factor of $f(k)$ when $k = 1$, so $(a + b)$ is a factor of $f(k+1)$, and so on for all natural numbers $k$.

Alternative Methods

(1) We want to prove for all odd integers $n> 0$ the statement $P(n)$ that $9^n + 1^n$ is a multiple of 10. $P(1)$ is true.

If $P(k)$ is true then consider $P(k+2)$: $$9^{k+2} + 1^{k+2} = 81(9^k + 1^k)-80$$ so $P(k+2)$ is true and the result is true for all odd numbers by the axiom of induction.

Similarly $7^1 + 3^1$ is a multiple of 10 and if $7^k + 3^k$ is a multiple of 10 then $$7^{k+2} + 3^{k+2} = 49(7^k) + 9(3^k) = 40(7^k) + 9(7^k + 3^k)$$ so this is also a multiple of 10 and the result is true for all odd numbers by the axiom of induction. Note that $9^2+1^2$ and $7^2+3^2$ are not multiples of 10 so the result is not true for even numbers.

(2) We have $8^0-2^0$ and $8^2-2^2$ are both multiples of 10. If $8^k-2^k$ is a multiple of 10 then $$8^{k+2} - 2^{k+2} = 64(8^k) - 4(2^k) = 60(8^k) +4(8^k-2^k)$$ so this is a multiple of 10 and the result is true for all even numbers. Similarly $6^2-4^2$ is a multiple of 10 and if $6^k-4^k$ is a multiple of 10 then $$6^{k+2} - 4^{k+2}= 36(6^k) - 16(4^k) = 20(6^k) + 16(6^k-4^k)$$ which is a multiple of 10 and so the result is true for all even numbers.

Note that $8 - 2$ and $6 - 4$ are not multiples of 10 and the result is not true for odd powers.

(3) The corresponding results are $9^n - 1^n$ and $7^n - 3^n$ are multiples of 10 when $n$ is an even number which can be proved by induction.

(4) Similarly $8^n + 2^n$ and $6^n + 4^n$ are multiples of 10 when $n$ is an odd number which can be proved by induction.

Proof using the Binomial Theorem

$$7^n + 3^n = 7^n + (10-7)^n = 7^n + 10^n + ..... + (-7)^n.$$ All the terms of the Binomial expansion involve powers of 10 apart from the term $(-7)^n$ so the expression is a multiple of 10 when $n$ is odd but not when $n$ is even. The same method works for all other parts of the question.