专题地图 › 递推数列
2014 年湖北预赛 · 第 1 题
F2填空题递推数列
已知正整数数列 {an} 满足 an+2=an+1+an(n∈N∗)。若 a11=157,则 a1=。
作答
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
标准答案:3
解析
提示
递推是相邻两项相加,因此把远处那一项反复展开,会得到两个初值的整数线性组合。
思路
初值均为正整数,先用大小限制把候选压成很少几个,再用整除或同余筛选;最后从初值正性确认整个递推都合法。
解答
递推展开得 a11=34a1+55a2=157。由正整数条件,1≤a2≤2。
模 34 得 21a2≡21(mod34),因 gcd(21,34)=1,故 a2≡1(mod34)。
于是 a2=1,a1=(157−55)/34=3。这两个正整数初值按递推生成全体正整数项,确实可行。
为什么评为 F2(会透露解法方向)
将递推前推成两个正整数初值的线性式,正性给有限界,同余排除其余候选;最后核初值能生成全体正项。
用到的方法(会透露解法方向)
核心工具:递推换元化成线性
专题卡:线性递推求通项:一阶减不动点,二阶用特征根