Question

Prove by induction:
5| (21^n+9)

Answer 1

It's kind of self-evident. Any power of 21 will have a 1 in the units place, and adding 9 to it makes it 0 and hence the number is divisible by 5.

To prove the claim by induction, first establish the base case. I assume
`n\in\Bbb N`, so for
`n=1` we have

`21^1 + 9 = 21 + 9 = 30`

and of course 30 = 5×6 is divisible by 5.

Assume the claim is true for
`n=k`, that
`5 \mid 21^k + 9`. This means that for some integer
`\ell`, we can write

`21^k + 9 = 5\ell`

Now the induction step: when
`n=k+1`, we have

`21^(k+1) + 9 = \bigg(21*(21^k + 9) - 9*21\bigg) + 9 \\\\ ~~~~~~~~~~~~~~ = 21*5\ell - 9*20 \\\\ ~~~~~~~~~~~~~~= 5*(21\ell - 9*4)`

which is divisible by 5. QED