递推 余数循环

hbghlyj

对任何非负整数$n$，$$35\nmid\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$

hbghlyj

回复 1# hbghlyj
math.stackexchange.com/questions/2415091
math.stackexchange.com/questions/16302
artofproblemsolving.com/community/c6h1617313p10113564
math.stackexchange.com/questions/822230
artofproblemsolving.com/community/c6h1601025p9962664
math.stackexchange.com/questions/913296
artofproblemsolving.com/community/c6h1524105p9122698
artofproblemsolving.com/community/c6h58616p358034

$a_n=\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$
递推公式$a_{n+2}=18a_{n+1}+49a_{n},a_1=11,a_2=149$
模35周期为6 (在上面的链接中, 是模5循环.)
1, 9, 1, 4, 16, 29...

---

事实上, 整数递推数列模任何数的余数都是循环的:
$a_n$是整数数列, 满足$a_{n+k}=f(a_{n+k-1},\cdots,a_n)$, 则$a_n\bmod m$是最终循环的.
证:
因为$\text{mod }m$的余数只有$m$个, 所以$(a_{n+k-1}\bmod m,\cdots,a_n\bmod m)$只有$m^k$个,
所以存在$1\le j\le m^k$使得$(a_{j+k}\bmod m,\cdots,a_j\bmod m)=(a_k\bmod m,\cdots,a_0\bmod m)$,
于是$f(a_{j+k}\bmod m,\cdots,a_j\bmod m)=f(a_k\bmod m,\cdots,a_0\bmod m)$,
即$a_{j+k+1}\equiv a_{k+1}\pmod m$
于是$f(a_{j+k+1}\bmod m,\cdots,a_{j+1}\bmod m)=f(a_{k+1}\bmod m,\cdots,a_1\bmod m)$,
即$a_{j+k+2}\equiv a_{k+2}\pmod m$
⋯
由此可得, 对任意正整数$i$, $a_{j+k+i}\equiv a_{k+i}\pmod m$

其妙

hbghlyj 发表于 2022-12-24 00:48
回复 1# hbghlyj
https://math.stackexchange.com/questions/2415091
https://math.stackexchange.com/que ...

如何判断循环周期？二阶线性递推数列有模周期公式吗？