数字串的通项公式

XIAOWEN

这个数列的通项公式可以使用求解线性递推关系来得到。根据数列的前几个数，我们可以列出如下的线性递推关系：

a(n) = 2*a(n-4) + 3*a(n-5) - 7*a(n-6) + 4*a(n-7) - 2*a(n-8)

其中n>=8，且a(0)=2, a(1)=3, a(2)=5, a(3)=8, a(4)=37, a(5)=45, a(6)=82, a(7)=127。

接下来需要利用这个递推关系来计算数列的第n项。

首先，我们可以将递推关系转化为矩阵形式：

| a(n)   |   | 2 0 0 0 3 -7 4 -2 |   | a(n-4) |
| a(n-1) |   | 1 0 0 0 0 3 -7  4 |   | a(n-5) |
| a(n-2) | = | 0 1 0 0 0 0  3 -7 | * | a(n-6) |
| a(n-3) |   | 0 0 1 0 0 0  0  3 |   | a(n-7) |
| a(n-4) |   | 0 0 0 1 0 0  0  0 |   | a(n-8) |
| a(n-5) |   | 0 0 0 0 1 0  0  0 |   |    0   |
| a(n-6) |   | 0 0 0 0 0 1  0  0 |   |    0   |
| a(n-7) |   | 0 0 0 0 0 0  1  0 |   |    0   |

对于任意的n>=8，我们可以通过矩阵乘法来计算a(n)：

| a(n)   |   | 2 0 0 0 3 -7 4 -2 |^(n-8)   | a(0) |
| a(n-1) |   | 1 0 0 0 0 3 -7 4 |         | a(1) |
| a(n-2) | = | 0 1 0 0 0 0 3 -7 |         | a(2) |
| a(n-3) |   | 0 0 1 0 0 0 0 3  |         | a(3) |
| a(n-4) |   | 0 0 0 1 0 0 0 0  |         | a(4) |
| a(n-5) |   | 0 0 0 0 1 0 0 0  |         | a(5) |
| a(n-6) |   | 0 0 0 0 0 1 0 0  |         | a(6) |
| a(n-7) |   | 0 0 0 0 0 0 1 0  |         | a(7) |

这个矩阵的n-8次方可以使用矩阵快速幂算法来计算，时间复杂度为O(log n)。因此，总时间复杂度为O(log n)。

综上所述，数列的通项公式为：

a(n) = [2 3 5 8 37 45 82 127] * M^(n-8)

其中M是递推关系对应的矩阵，用于计算矩阵的n-8次方。

XIAOWEN

可以使用数学归纳法来证明递推关系的正确性

王守恩

nyy 发表于 2023-5-15 11:44
代码写出来了，但是求解结果不很满意

\[\text{DifferenceRoot}[\{%unicode{f818},%unicode{f80d}\ ...

{2,3,5,8,37,45,82,127,590,717,1307,2024,9403,11427,20830,32257,149858,182115,331973,514088}

1. Numerator[Convergents[Sqrt[7], 20]]

复制代码

王守恩

谢谢Treenewbee！ OEIS落后了。 谢谢Treenewbee！

Table\(\bigg[\)CoefficientList\(\bigg[\)Series\(\bigg[\)\(\D\frac{1}{1 - x^n - x^{2n}}, {x, 0, 24 n}\bigg], x\bigg], {n, 1, 4}\bigg]\)

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025},
{1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, 13, 0, 21, 0, 34, 0, 55, 0, 89, 0, 144, 0, 233, 0, 377, 0, 610, 0, 987, 0, 1597, 0, 2584, 0, 4181, 0, 6765, 0, 10946, 0, 17711, 0, 28657, 0, 46368, 0, 75025},
{1, 0, 0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 5, 0, 0, 8, 0, 0, 13, 0, 0, 21, 0, 0, 34, 0, 0, 55, 0, 0, 89, 0, 0, 144, 0, 0, 233, 0, 0, 377, 0, 0, 610, 0, 0, 987, 0, 0, 1597, 0, 0, 2584, 0, 0, 4181, 0, 0, ......
{1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 8, 0, 0, 0, 13, 0, 0, 0, 21, 0, 0, 0, 34, 0, 0, 0, 55, 0, 0, 0, 89, 0, 0, 0, 144, 0, 0, 0, 233, 0, 0, 0, 377, 0, 0, 0, 610, 0, 0, 0, 987, ........

王守恩

1. Solve[{x^2 + x*y - y^2 == 1, 30000 > x}, {x, y}, PositiveIntegers]

复制代码

{{x -> 1,  y -> 1}, {x -> 2,  y -> 3}, {x -> 5,  y -> 8}, {x -> 13,  y -> 21}, {x -> 34,  y -> 55}, {x -> 89,  y -> 144}, {x -> 233,
y -> 377}, {x -> 610, y -> 987}, {x -> 1597, y -> 2584}, {x -> 4181, y -> 6765}, {x -> 10946, y -> 17711}, {x -> 28657, y -> 46368}}

northwolves

王守恩 发表于 2023-6-18 10:58
{{x -> 1,  y -> 1}, {x -> 2,  y -> 3}, {x -> 5,  y -> 8}, {x -> 13,  y -> 21}, {x -> 34,  y -> 55} ...

$x= \frac{1}{2} \left(\sqrt{5 y^2+4}-y\right)$
$y=\frac{1}{2}\left(\sqrt{5 x^2-4}+x\right)$

northwolves

1. Select[Range@100000, IntegerQ[Sqrt[5*#^2 + 4]] &]

复制代码

{1,3,8,21,55,144,377,987,2584,6765,17711,46368}

王守恩

northwolves 发表于 2023-6-18 12:13
{1,3,8,21,55,144,377,987,2584,6765,17711,46368}

a(04)=1, 1+1+1+1,
a(06)=1, 1+1+1+3,
a(08)=2, 1+1+1+5=1+1+3+3,
a(10)=3, 1+1+1+7=1+1+3+5=1+3+3+3,
a(12)=5, 1+1+1+9=1+1+3+7=1+1+5+5=1+3+3+5=3+3+3+3,
a(14)=6, 1+1+1+11=1+1+3+9=1+1+5+7=1+3+3+7=1+3+5+5=3+3+3+5,
a(16)=9, 1+1+1+13=1+1+3+11=1+1+5+9=1+1+7+7=1+3+3+9=1+3+5+7=1+5+5+5=3+3+3+7=3+3+5+5,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(1)

a(04)=1, 1+1+1+1,
a(07)=1, 1+1+1+4,
a(10)=2, 1+1+1+7=1+1+4+4,
a(13)=3, 1+1+1+10=1+1+4+7=1+4+4+4,
a(16)=5, 1+1+1+13=1+1+4+10=1+1+7+7=1+4+4+7=4+4+4+4,
a(19)=6, 1+1+1+16=1+1+4+13=1+1+7+10=1+4+4+10=1+4+7+7=4+4+4+7,
a(22)=9, 1+1+1+19=1+1+4+16=1+1+7+13=1+1+10+10=1+4+4+13=1+4+7+10=1+7+7+7=4+4+4+10=4+4+7+7,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(2)

a(04)=1, 1+1+1+1,
a(08)=1, 1+1+1+5,
a(12)=2, 1+1+1+9=1+1+5+5,
a(16)=3, 1+1+1+13=1+1+5+9=1+5+5+5,
a(20)=5, 1+1+1+17=1+1+5+13=1+1+9+9=1+5+5+9=5+5+5+5,
a(24)=6, 1+1+1+21=1+1+5+17=1+1+9+13=1+5+5+13=1+5+9+9=5+5+5+9,
a(28)=9, 1+1+1+25=1+1+5+21=1+1+9+17=1+1+13+13=1+5+5+17=1+5+9+13=1+9+9+9=5+5+5+13=5+5+9+9,
得到这样一串数: 1,1,2,3,5,6,11,15,18,23,27,34,......(3)

(1),(2),(3)可有通项公式？(1),(2),(3)可以是同一串数？

northwolves

1. Array[Length@IntegerPartitions[#-1, 4] &, 50]

复制代码

{1,1,2,3,5,6,9,11,15,18,23,27,34,39,47,54,64,72,84,94,108,120,136,150,169,185,206,225,249,270,297,321,351,378,411,441,478,511,551,588,632,672,720,764,816,864,920,972,1033,1089,1154}

northwolves

或者

1. 
   
2. CoefficientList[Series[1/Product[1 - x^k, {k, 4}], {x, 0, 49}], x]

复制代码