Inductive proof that every term is a sequence is divisible by 16

Question

I have this question:

The $n$^th member $a_n$ of a sequence is defined by $a_n = 5^n + 12n -1$. By considering $a_{k+1} - 5a_k$ prove that all terms of the sequence are divisible by 16.

I can do the induction and have managed to rearrange the expression at the inductive step such that the expression must be divisible by 16. In other words, I can do the question fine. My question is: why must we consider $a_{k+1} - 5a_k$? Why can't we prove this by induction just by looking at $a_{k+1}$? Also, how can it be deduced that the expression we must consider is $a_{k+1} - 5a_k$?

Answer 1

It is much more pleasant to look at $a_{k+1}-5a_k$, since the annoying power of $5$ disappears. But we can fail to notice that and still push things through. It will involve more work. We have $$5^{k+1}+12(k+1)-1=5^k+12k-1 +5^{k+1}-5^k+12.$$ We want to show that $5^{k+1}-5^k+12$ is divisible by $16$.

Note that $5^{k+1}-5^k=4\cdot 5^k$. If we can show that $5^k$ is of the form $4t+1$, it will follow that $5^{k+1}-5^k+12$, which is $4(4t+1)+12$, is divisible by $16$.

How do we show that $5^k$ has remainder $1$ on division by $4$? There are many ways, including a straightforward induction.

Alternately, we work directly with $4\cdot 5^k+12$. By the induction hypothesis, $5^k+12k-1$ is $16w$ for some $w$. Then $5^k=16w-12k+1$, and therefore $4\cdot 5^k +12=4(16w-12k+1)+12$, which is easily seen to be divisible by $16$.

Answer 2

If you prove that $a_n$ (or $a_{n+1}$, doesn't matter) is divisible by 16, that is a direct proof.

For a proof with induction, you first need to check that $a_0$ is divisible by 16.

Then assuming that $a_n$ is divisible by 16, you need to prove that $a_{n+1}$ is divisible by 16. And how do you do that?

If you know that 16 divides $a_n$, and if you know 16 divides $a_{n+1}-5a_n$ then that means that $a_{n+1}$ is also divisible by 16, which completes the proof.

Answer 3

You can do it "directly" as follows. $16$ divides $a_1=16$. By induction assume $16$ divides $a_{n-1}$.

$5a_{n-1}=5^n+60n-5$

$a_n=5a_{n-1}-60n+5+12(n+1)-1=5a_{n-1}-48n+16$

$16$ divides $48$, $16$ and $a_{n-1}$ (induction). So $16$ divides $a_n$.

Basically, $5a_{n-1}$ appears when you try to write $a_n$ in terms of $a_{n-1}$. Alternatively, $a_n=a_{n-1}+12+5^{n}-5^{n-1}=a_{n-1}+4 (5^{n-1}+3)$ and so you need to show $4$ divides $5^{n-1}+3$ either by induction or modular arithmetic.

Answer 4

You do not have to use recursion. For example you could note

     n   a_n = 5^n + 12n - 1
     0           0
     1          16
     2          48
     3         160
     4         672
     5        3184
     6       15696
     7       78208
     8      390720
     9     1953232
    10     9765744
    11    48828256
    12   244140768
    13  1220703280
    14  6103515792
    15 30517578304

are all equal to $0$ modulo $16$ and so this continues for all integers modulo $16$.

But the recursion is fairly obvious: the $5^n$ term dominates for large $n$ so $a_{n+1}$ is close to $5a_n$ and it is natural to look at the difference.

Alternative things you might consider for induction are $$a_{k+2}-6a_{k+1}+5a_k$$ or $$a_{k+3}-7a_{k+3}+11a_{k+1}-5a_k$$ but you would need to deal with more initial terms and more manipulation, so it is probably not worth it.

Answer 5

A simple proof with some arithmetic modulo $16$:

$$\begin{array}{r|ccc} n\equiv\pmod 4\quad & 5^n & 12n-1& a_n \\ \hline 0 & 1 & -1 & 0 \\ 1 & 5 & 11 & 0 \\ 2 & 9 & 7 & 0 \\ 3 & 13 & 3 & 0 \end{array}$$