求证：$9\mid (3n+1)7^n-1$

isee

源自知乎提问


构造数列

$$\{a_n\}:a_1=27,\ a_2=342\ ,a_{n+2}=14a_{n+1}-49a_{n}-36,$$

由数学归纳法易知 $9\mid a_n.$

另一方面

\begin{align*} a_{n+2}&=14a_{n+1}-49a_{n}-36\\[1em] \iff a_{n+2}+1&=14(a_{n+1}+1)-49(a_{n}+1)\\[1em] \iff a_{n+2}+1-7a_{n+1}&=7\left((a_{n+1}+1)-7(a_{n}+1)\right)\\[1em] \therefore \ a_{n+1}+1-7(a_{n}+1)&=(343-7\times 28)\cdot 7^{n-1}=3\cdot 7^{n+1}\\[1em] \iff \frac{\ a_{n+1}+1}{7^{n+1}}-\frac {a_{n}+1}{7^n}&=3\\[1em] \therefore \ a_n+1&=(1+3n)\cdot 7^n\\[1em] a_n&=(3n+1)7^n-1. \end{align*}

即 $9\mid (3n+1)7^n-1.$

tommywong

$7^n\equiv (1+2\times 3)^n\equiv 1+6n\pmod{9}$
$(3n+1)7^n-1\equiv (3n+1)(1+6n)-1\equiv 0\pmod{9}$

isee

回复 2# tommywong

哈哈哈哈哈，数论真是两行十几秒种，理解几分钟；我是数列很多行几分钟，理解也是几分钟~~~~~~~~

kuing

回复 3# isee

`(1+2\times 3)^n\equiv 1+6n\pmod{9}` 用二项式定理就能理解了，后面都是显然，用不了几分钟来理解啊