高中数列题目

mathe

上面过程为了转化为已经研究过的以曲线$xy=1$为基础的分析过程，产生了大量额外的计算，特别引入的常数h使得计算过程大大复杂化。
经过对以前计算过程的回顾以后，觉得应该可以直接在曲线$y=x^2$上重新计算，计算量应该会小很多。
7#中已经给出对于曲线$y=x^2$采用第一类变换曲线$6x^2+y^2-10y+1=0$进行变换可以将点$(a_{n-1},a_{n-1}^2)$变化为$(a_n,a_n^2)$
我们定义第一类变换曲线$C_t: x^2-y+t(5x^2+y^2-9y+1)=0$, 于是t=0对应$y=x^2$上的恒等变换，t=1就对应将$(a_{n-1},a_{n-1}^2)$变化为$(a_n,a_n^2)$的变换。
$C_t: (1+5t)x^2+ty^2+(-1-9t)y+t=0$,其系数矩阵为\(\begin{bmatrix}1+5t&0&0\\0&t&\frac{-1-9t}2\\0&\frac{-1-9t}2&t\end{bmatrix}\)
假设变换$C_t$和$C_t$的复合变换为$C_s$
设点$(x_1,x_1^2)$经过$C_t$变化为$(x_2,x_2^2)$,再经过$C_t$变化为$(x_3,x_3^2)$, 于是$(x_1,x_1^2)$经过$C_s$直接变化为$(x_3,x_3^2)$
根据7#中推导结果，可以得出
\(\begin{cases}\begin{pmatrix}-(x_1+x_2)&1&x_1x_2\end{pmatrix}\begin{bmatrix}1+5t&0&0\\0&t&\frac{-1-9t}2\\0&\frac{-1-9t}2&t\end{bmatrix}^{-1}\begin{pmatrix}-(x_1+x_2)\\1\\x_1x_2\end{pmatrix}=0\\
\begin{pmatrix}-(x_2+x_3)&1&x_2x_3\end{pmatrix}\begin{bmatrix}1+5t&0&0\\0&t&\frac{-1-9t}2\\0&\frac{-1-9t}2&t\end{bmatrix}^{-1}\begin{pmatrix}-(x_2+x_3)\\1\\x_2x_3\end{pmatrix}=0\\\begin{pmatrix}-(x_1+x_3)&1&x_1x_3\end{pmatrix}\begin{bmatrix}1+5s&0&0\\0&s&\frac{-1-9s}2\\0&\frac{-1-9s}2&s\end{bmatrix}^{-1}\begin{pmatrix}-(x_1+x_3)\\1\\x_1x_3\end{pmatrix}=0
\end{cases}\)
我们选择$x_2=0$代入前两式，得到$x_1,x_3$必须同时满足二次方程:
$(77t^2 + 18t + 1)x^2 - (20t^2 + 4t)=0$
于是根据韦达定理得出$x_1+x_3=0, x_1x_3=-\frac{20t^2 + 4t}{77t^2 + 18t + 1}$
由此得出方程
\(\begin{pmatrix}0&77t^2 + 18t + 1&-(20t^2 + 4t)\end{pmatrix}\begin{bmatrix}\frac{-77s^2-18s- 1}{5s + 1}&0&0\\0&4s&18s+2\\0&18s+2&4s\end{bmatrix}\begin{pmatrix}0\\77t^2 + 18t + 1\\-(20t^2 + 4t)\end{pmatrix}=0\)
即\(\begin{pmatrix}77t^2 + 18t + 1&-(20t^2 + 4t)\end{pmatrix}\begin{bmatrix}4s&18s+2\\18s+2&4s\end{bmatrix}\begin{pmatrix}77t^2 + 18t + 1\\-(20t^2 + 4t)\end{pmatrix}=0\)
得出\(s=\frac{-1540t^4 - 668t^3 - 92t^2 - 4t}{7531t^4 + 3080t^3 + 334t^2 - 1}\)
显然如果有某个$t$使得将点$(a_0,a_0^2)=(0,0)$变换为$(a_n,a_n^2)$,于是代入前面第一式得出
$(77t^2 + 18t + 1)a_n^2 - (20t^2 + 4t)=0$,
而对应的$s$会将点$(a_0,a_0^2)$变换为$(a_{2n},a_{2n}^2)$,得出
$(77s^2 + 18s + 1)a_{2n}^2 - (20s^2 + 4s)=0$
代入$a_{2n}$和$a_n$的关系式验算通过。

mathe

上面过程只是验算了$a_{2n}$和$a_n$的关系，但是对于一般的递推情况，然后要求出$a_{2n}^2$和$a_n^2$的关系式还不够。
注意到上面推导过程得出了\(x_1x_3=-\frac{20t^2+4t}{77t^2+18t+1}\),这个函数式比较重要，我们记为\(r(t)=\frac{20t^2+4t}{77t^2+18t+1}\)
于是我们得出
\(\begin{pmatrix}0&1&-r(t)\end{pmatrix}\begin{bmatrix}\frac{-77s^2-18s- 1}{5s + 1}&0&0\\0&4s&18s+2\\0&18s+2&4s\end{bmatrix}\begin{pmatrix}0\\1\\-r(t)\end{pmatrix}=0\)
即\(\begin{pmatrix}1&-r(t)\end{pmatrix}\begin{bmatrix}4s&18s+2\\18s+2&4s\end{bmatrix}\begin{pmatrix}1\\-r(t)\end{pmatrix}=0\)
得出\(s=\frac{r(t)}{r(t)^2-9r(t)+1}\)
而后面的推导过程得出\(a_n^2=r(t), a_{2n}^2=r(s)=r(\frac{r(t)}{r(t)^2+9r(t)+1})=r(\frac{a_n^2}{a_n^4+9a_n^2+1})\)
得到结果。
于是对于一般的递推关系，也有可能可以重复上面流程进行计算得出$a_{2n}^2$关于$a_n^2$的表达式（依赖于上面带参数t的矩阵求逆情况）

mathe

上面计算过程中得到的函数r(t)是一个分子和分母都是t的二次函数的分式，这个也是必然的，而不是偶然情况。
由于变换曲线$C_t$的矩阵可以写成$J+tK$的形式，根据链接， 在复数范围存在合同变换使得两个矩阵J,K同时对角化，这个只要通过计算$J^{-1}K$的特征值和特征向量就可以得到。
于是我们可以设$J=P^T MP, K=P^T NP$,其中M,N都是对角阵，第一次令$x_2=0$代入后的方程就变成了\(\sum_{h=1}^3 \frac{(a_h x+b_h)^2}{c_h t+d_h}=0\)展开去分母后是x的二次函数，其个系数都是t的不超过2次的多项式，于是根据韦达定理,向量$(-(x_1+x_3): 1:x_1x_3)$可以转化为每项都是t的二次函数,而s依次是一个分子分母都是四次的分式，$a_n$是一个一次项系数可能不为0的二次函数，无法得出题目中这么好的性质，通过消元还是能得出$a_{2n}$和$a_n$的关系式，但是会复杂很多。而题目中这么良好性质的本质是要求J,K的第一行和第一列都只有第一个元素非零。当然满足这样优秀性质的递推情况我们可以构造很多个，其中有三个自由参数可选

mathe

现在我们试着更换一条曲线，比如把$C_2$换成$4x^2+y^2-8y+F=0$
于是$C_t$的对应矩阵变换为:\(\begin{bmatrix}1+3t&0&0\\0&t&\frac{-1-7t}2\\0&\frac{-1-7t}2&Ft\end{bmatrix}\)
可以得出$r(t)=(12Ft^2 + 4Ft)/((49-4F)t^2+14t+1)$
由于$a_1^2=r(1)=\frac{4F}{16-F}$
为了形式简单，我们需要选择F使得$a_1$为有理数，比如选择$a_1=1$,于是$F=\frac{16}5$
于是$C_2$选择为$20x^2+5y^2-40y+16=0$
由于$a_{n-1},a_{n+1}$都满足
\(\begin{pmatrix}-(x+a_n)&1&xa_n\end{pmatrix}\begin{bmatrix}4&0&0\\0&1&-4\\0&-4&\frac{16}5\end{bmatrix}^{-1}\begin{pmatrix}-(x+a_n)\\1\\xa_n\end{pmatrix}=0\)
即\((-\frac5{64}a_n^2 + \frac14)x^2 - \frac18a_n x + \frac14a^2 - \frac14=0\)
根据韦达定理得出递推式
\(a_{n-1}+a_{n+1}=\frac{8a_n}{-5a_n^2 + 16}\), 而初始条件为$a_0=0,a_1=1$
另外可以计算得到\(r(t)=\frac{192t^2 +64t}{181t^2+70t+5}\)
以及\(s=\frac{5r(t)}{5r(t)^2-35r(t)+16}\),

得到\(a_{2n}^2= r(s)=r(\frac{a_n^2}{a_n^4-7a_n^2+3})=\frac{64(5a_n^4-20a_n^2+16)a_n^2}{(5a_n^4-16)^2}\)

mathe

上面递推式可以改为在$10^8+7$阶素数域内进行计算
已知$a_0=0,a_1=1, a_{n+1} -= \frac{8a_n}{16-5a_n^2}-a_{n-1} (mod (10^8+7))$, 比如求$a_{10^8}$

mathe

为了达成15#的计算目标，除了14#中给出将两次$C_t$变换复合成一次$C_s$时s和t的关系式以外（相当于给出了从$a_n$计算$a_{2n}$的方案）
我们还需要寻找将$C_1$和$C_t$变换复合以后得出$C_s$时s和t的关系式。
经计算可以知道15#的方案中$a_0=0,a_1=1,a_2=8/11$
将$C_1$和$C_t$变换复合以后得出$C_s$代表$a_1$经过$C_t$的变换结果和$a_0$讲过$C_s$的变化结果相等，假设它们都变化为x,得到
\(\begin{pmatrix}-(0+x)&1&0*x)\end{pmatrix}C_t^{-1}\begin{pmatrix}-(0+x)\\1\\0*x)\end{pmatrix}=0\)
\(\begin{pmatrix}-(1+x)&1&1*x)\end{pmatrix}C_s^{-1}\begin{pmatrix}-(1+x)\\1\\1*x)\end{pmatrix}=0\)
从中消去变量x得到关系式
\((334274353s^4 + 212088732s^3 + 28000006s^2 - 1843620s + 3025)t^4 + (212088732s^4 + 128666128s^3 + 12728360s^2 - 2206960s - 3300)t^3 + (28000006s^4 + 12728360s^3 - 1946780s^2 - 1031000s - 1850)t^2 + (-1843620s^4 - 2206960s^3 - 1031000s^2 - 162800s + 1500)t + (3025s^4 - 3300s^3 - 1850s^2 + 1500s + 625)=0\)
很遗憾，次数是4次而不是2次，显然还不唯一确定。这个是因为仅给出$a_0\to a_1$并不能唯一确定变换 ($C_s$是经过四个点的二次曲线系中一条，其中变换$a_0\to a_1$相当于要求这条曲线还要和经过$(a_0,a_0^2), (a_1,a_1^2)$的直线相切，经过四点并且和给定直线先切的二次曲线会有两条，所以不能唯一确定。另外我们可以扩展定义$a_{-1}=-1$, 但是下面过程使用计算更麻烦的$a_1\to a_2$而不是$a_{-1}\to a_0$是因为这一族曲线比较特殊，全部关于y轴对称，条件$a_{-1}\to a_0$和$a_0\to a_1$的约束是对称的，会产生相同的结果）
于是我们可以继续使用条件$a_2$经过$C_t$的变换结果和$a_1$经过过$C_s$变换得到的结果相同，类似上面的方案计算，可以得出
\((1199553377409s^4 + 845837483868s^3 + 75368220646s^2 - 25560424420s + 42837025)t^4 + (845837483868s^4 + 787619258128s^3 + 152444979880s^2 - 7647358960s - 88619300)t^3 + (75368220646s^4 + 152444979880s^3 + 47645318820s^2 + 683426600s + 48778150)t^2 + (-25560424420s^4 - 7647358960s^3 + 683426600s^2 - 193410800s - 3046500)t + (42837025s^4 - 88619300s^3 + 48778150s^2 - 3046500s + 50625)=0\)
计算两者的公因式得出s和t这时的关系式为
\((42599s^2 + 14770s - 25)t^2 + (14770s^2 + 5660s + 50)t + (-25s^2 + 50s - 25)=0\)

于是后面，假设$C_1$复合n次得到的曲线为$C_{t_n}$,于是我们可以得出\(t_{2n}=\frac{5r(t_n)}{5r(t_n)^2-35r(t_n)+6}\)   (1)
而$t_{n-1},t_{n+1}$都满足方程\((42599t_n^2 + 14770t_n - 25)x^2 + (14770t_n^2 + 5660t_n + 50)x + (-25t_n^2 + 50t_n - 25)=0\)  (2)
然后为了我们任何时候可以通过$t_n, t_{n+1}$计算出$t_{2n},t_{2n+1},t_{2n+2}$
也就是先通过公式(1)得出$t_{2n},t_{2n+2}$, 然后对$t_{2n}, t_{2n+2}$采用公式(2)同时得出一个二次方程，它们的公因子必然是x的一次函数，有唯一解$t_{2n+1}$.
然后根据需要保留$t_{2n},t_{2n+1}$或$t_{2n+1},t_{2n+2}$,计算扩展计算知道找到需要的$t_{m-1},t_m$。然后对$a_1$应用$t_{m-1}$和$a_0$应用$t_m$,两者得出的二次方程的公共根就是$a_m$

wangxinyue

学习中

wangxinyue

数列是重要的基础概念，要学习中提升认知。

mathe

利用计算对合变换的链接28#中的附件可以得出一种更一般化的有效计算方法。
还是以15#的数据为例子，我们已经转化为目标曲线为\(y=x^2\),
第一类变换曲线为\(4x^2+y^2-8y+\frac{16}5\)
更具附件中符号，对应
\(J=\begin{bmatrix}1&0&0\\0&0&-\frac12\\0&-\frac12&0\end{bmatrix}\)
以及
\(K=\begin{bmatrix}4&0&0\\0&1&-4\\0&-4&\frac{16}5\end{bmatrix}\)
矩阵\(J^{-1}K\)的特征多项式为\(x^3 - 20x^2 + \frac{576}5x - \frac{1024}5=(x-4)(x^2-16x+\frac{256}5)\)
设h为\(x^2-16x+\frac{256}5=0\)的一个根，比如\(r\approx 4.422291236...\)

记\(r_3=4,r_1=r,r_2=16-r\),根据附件结论有\(a=1-\frac{r}4, b=1-\frac{16-r}4, u_3=4,u_2=20,u_1=\frac{576}5,u_0=\frac{1024}5\)
而h=0代表基本变换，一般情况对应的变换曲线为\(K_h=h(x^2-y)+(4x^2+y^2-8y+\frac{16}5)\)。
由于h=0代表基本变换，对应椭圆曲线\(y^2=\frac{1024}5(x^3 + 20x^2 + \frac{576}5x + \frac{1024}5)\)上基本点\((0,\frac{1024}5)\)
这个曲线不适合pari/gp计算，我们选择变换\(Y=\frac{1024}5 y, X=\frac{1024}5x\),得到
\(Y^2=X^3+20\times\frac{1024}5X^2+\frac{576}5(\frac{1024}5)^2 X+(\frac{1024}5)^2)^4\)
初始迭代点\(X=0,Y=(\frac{1024}5)^2\).
在pari/gp中可以使用命令
?E=ellinit([0,20*1024/5,0,(1024/5)^2*(576/5), (1024/5)^4]);
?A=[0,(1024/5)^2];
?ellmul(E,A,2)
[-19456/25, 360448/125]
对应会原坐标x=-19/5.
所以就是两次变换的复合对应h=-19/5， 即第一类变换曲线为$K_{-19/5}$ : \(\frac15 x^2+y^2-\frac{21}5y+\frac{16}5=0\)
我们需要过$(a_0,a_0^2)=(0,0)$向这个曲线做切线，切点在(0,0)关于$K_{-19/5}$的极线\(-\frac{21}{10}y+\frac{16}5=0\)上，即$y=\frac{32}{21}$上
，即切点为\((\pm\frac{44}{21},\frac{32}{21})\)
对应切线方程\(\pm\frac{44}{105} x-\frac{121}{210}y=0\),即\(y=\pm\frac{8}{11}x\)再求和曲线\(y=x^2\)的交点，
所以得出解\(x=\pm \frac{8}{11}\)，也就是获得\(|a_2|=\frac{8}{11}\)， 当然这个方法的缺点是最后出来会有两个候选解，但是如果我们只需要$a_n^2$或$|a_n|$，用这方法很方便。但是如果需要判断到底那个解，那么还是需要前面类似的方法，每步迭代过程总是计算两个相邻的解再加以判断。

而这种方法还有一个好处，比如对于15#给出的数据，如果我们需要计算第$10^8$项，由于添加了模素数$10^8+7$
我们可以先计算椭圆曲线的阶
?E=ellinit([0,20*1024/5,0,(1024/5)^2*(576/5), (1024/5)^4], 10^8+7);
?ellcard(E)
99994442
也就是我们只要改为计算第$5558$项即可。
? ellmul(E,A,5558)
[Mod(53676673, 100000007), Mod(82414574, 100000007)]
对应h=53676673/(1024/5)=23406626:
   Mod(23406630, 100000007)*x^2 + (y^2 + Mod(76593373, 100000007)*y + Mod(40000006, 100000007))=0
(0,0)对应的极线为y=Mod(4942312, 100000007),得出切点坐标x=Mod(17689020, 100000007)或相反数
对应切线方程y=Mod(62576473, 100000007)*x,代入方程$y=x^2$得到x=Mod(62576473, 100000007).
由此得出$a_{10^8}$是62576473或37423534而$a_{10^8}^2=99012707$

密码学中，我们喜欢采用阶数含有大素因子的椭圆曲线做加解密运算。上面的椭圆曲线阶99994442不是很好，因子太多，最大素因子不够大。
这个曲线类中，$a_n$和$-a_n$总是对称出现的，这导致阶必然是2的倍数，所以我们最好能找到的阶是一个素数的2倍。
比如我们替换上面的模$10^8+7$为下面这些素数，可以使得椭圆曲线的阶为2的倍数。

素数域	椭圆曲线的阶
$2^128-44999=340282366920938463463374607431768166457$	$2\times170141183460469231723317694944204913313$
$2^128-36273=340282366920938463463374607431768175183	$2\times170141183460469231747828929037523766563$
$2^128+4641=340282366920938463463374607431768216097	$2\times170141183460469231733791976672803792673$
$2^128+16597=340282366920938463463374607431768228053	$2\times170141183460469231719162321042991111529$

然后在这些曲线上，我们就可以改用一个整数$a_n^2$代表椭圆曲线上每两个点了。

王守恩

把这串数的前12项写出来(3楼好像出不来)。
RecurrenceTable[{a[0]=0,a[1]=1/2,a[n+1]+a[n-1]=(2a[n])/(4-a[n]^2)},a,{n,12}]
{0,
1/2,
4/15,
-(161/442),
-(22920/50369),
2706401/21771082,
19401465356/37495194255,
36867352480319/241014273471602,
-(2713767869349580560/6160584655684657921),
-(230411421854480432456639/599328309772220125192082),
54108065494048984622972655124/224603401396311977137287538575,
168116478779528111798480001300551839/331803229851166469627898043962250282,
54690892794338807630186727222541308756840/1834835894556507914114598176948580439476929}