Kolejny problem z podzielnością

                     Na stronie 301 mamy Problem 1

In translation

"Show that for every natural number $n$, the number $4^n+15n-1$ is divisible by 9."

          So in the previous post, we solved it by two methods.

          I. By Mathematical Induction, let $c_n=4^n+15n-1$. For $n=0$ we have $c_0=0 \;\vdots\;9$.

Assuming $c_n\;\vdots\;9$, we have $c_{n+1}=4^{n+1}+15\cdot(n+1)-1=4\cdot 4^n+15n+14=$

$=4(c_n-15n+1)+15n+14=4c_n-45n+18\;\vdots\;9$ because each of the terms $4c_n,\;45n,\;18$ is divisible by 9, so so is their sum.

          II. With Newton's Binomial Formula

$$4^n=(3+1)^n=\sum_{k=0}^{n-2}\binom{n}{k}\cdot3^{n-k}\cdot1^k+\binom{n}{n-1}\cdot3^1\cdot 1^{n-1}+1^n=9\cdot a+3n+1$$

because in the first sum all the terms contain a factor $3^p,\;p=n,\;n-1,\dots,\;2$.

$\Rightarrow\; c_n=(9a+3n+1)+15n-1=9a+18n=9(a+2n)\;\vdots\;9.$

$\blacksquare$