求通项公式

aimisiyou

已知a₀=2,a_n+1=a_n+[a_n/2],求a_n=?   ([]为取整函数，如[5/2]=2,[10/2]=5)

补充内容 (2015-4-20 23:17):
刚开始学编辑数学公式，为了美观再写一下。\(b_2=4,\;b_{n+1}=b_n+\left[\frac{b_n}{2}\right]\),求 \(b_n\)

282842712474

这道题，基本就是对着
http://spaces.ac.cn/index.php/archives/3064/
抄一次。原始来源是@kastin 大神
http://bbs.emath.ac.cn/forum.php ... amp;page=1#pid55470
一个可选的答案是
$$a_n=\left\lceil \beta \left(\frac{3}{2}\right)^n\right\rceil,\quad \beta=1.622270502884...$$
其中\(\left\lceil \cdot\right\rceil\)是上取整函数。

282842712474

把通项公式改为
$$a_{n+1}=\frac{3}{2}a_n-\frac{\theta_n}{2}$$
其中
$$\theta_n=\left\{\begin{aligned}1,\, a_n\text{是奇数}\\
0,\, a_n\text{是偶数}\end{aligned}\right.$$
迭代得
$$\begin{aligned}a_n=&\left(\frac{3}{2}\right)^n a_0-\sum_{k=0}^{n-1} \frac{\theta_k}{2}\left(\frac{3}{2}\right)^{n-1-k}\\
=&\left(\frac{3}{2}\right)^n \left[a_0-\sum_{k=0}^{\infty} \frac{\theta_k}{2}\left(\frac{3}{2}\right)^{-1-k}\right]+\sum_{k=n}^{\infty}\frac{\theta_k}{2}\left(\frac{3}{2}\right)^{n-1-k}\end{aligned}$$
记
$$\beta=a_0-\sum_{k=0}^{\infty} \frac{\theta_k}{2}\left(\frac{3}{2}\right)^{-1-k}$$
则易知
$$a_n > \beta\left(\frac{3}{2}\right)^n$$
以及
$$a_n < \beta\left(\frac{3}{2}\right)^n + \sum_{k=n}^{\infty}\frac{1}{2}\left(\frac{3}{2}\right)^{n-1-k} =\beta\left(\frac{3}{2}\right)^n+1$$
又由于$a_n$均是整数，所以$a_n$与\(\beta\left(\frac{3}{2}\right)^n\)的关系是上取整。
其中，$\beta$可以由上面公式算，也可以由下面的关系直接算
$$\beta=\lim_{n\to\infty} \frac{a_n}{(3/2)^n}$$

当然，这只是形式上的公式，毕竟求$\beta$需要知道各$a_n$了。

aimisiyou

282842712474 发表于 2015-4-20 11:15
把通项公式改为
$$a_{n+1}=\frac{3}{2}a_n-\frac{\theta_n}{2}$$
其中

比如说采用这种近似公式$$a_n=\left\lceil \beta \left(\frac{3}{2}\right)^n\right\rceil,\quad \beta=1.622270502884...$$
其中\(\left\lceil \cdot\right\rceil\)是上取整函数。，$$a_1-a_2-a_3……a_n$$都正确,但从$$a_{n+1}$$开始不准确了，能判断n的上限吗？

282842712474

aimisiyou 发表于 2015-4-20 12:34
比如说采用这种近似公式，$$a_1-a_2-a_3……a_n$$都正确,但从$$a_{n+1}$$开始不准确了，能判断n的上限 ...

这不是近似，原则上来说，可以算出$\beta$的无穷位小数，而对于精确的$\beta$，这个公式对于所有$n$都成立

aimisiyou

282842712474 发表于 2015-4-20 13:00
这不是近似，原则上来说，可以算出$\beta$的无穷位小数，而对于精确的$\beta$，这个公式对于所有$n$都 ...

不可能进行无穷位数运算吧，
如果系数保留五位小数公式准确到\(a_n\), \(n\) 最大为多少？
如果系数保留六位小数公式准确到\(a_m\),\(m\)最大为多少？

282842712474

aimisiyou 发表于 2015-4-20 14:04
不可能进行无穷位数运算吧，如果系数保留五位小数公式准确到$$a_n$$,n最大为多少？如果系数保留六位小数 ...

为什么不行？计算足够多的a_n就能够计算足够多的位数。当然，这涉及到一个循环论证的问题。但是，这个系数确实是精确存在的，我们能不能计算出它来，只是我们的能力问题。

假设发现β正好等于自然对数的底e，那么你觉得这个答案是不是精确的？

当然，你思考的问题(精确度跟有效的n)也有一定的意义，但我觉得没多大必要。

aimisiyou

282842712474 发表于 2015-4-20 15:02
为什么不行？计算足够多的a_n就能够计算足够多的位数。当然，这涉及到一个循环论证的问题。但是，这个系 ...

谢谢，领略了另一种计算方式。本来是研究编程实现约瑟夫数圈问题（n个人围成一圈，从第一位开始按1、2 、3、……m循环报数，凡报1的出圈，求最后一位出圈者原来排在的位置？）分析可得到递推关系$$a_2=2$$ $$a_n=2+(a_{n-1}+m-2)\mod{(n-1)}$$,根据递推关系求\(a_n\)
但当\(n\)较大时循环次数多，运行效率低，故想能否有简洁公式提高运行效率？
此例只是取当\(m=3\)时的情况，运行效率对比递归方法有很大提高！

aimisiyou

往前进一步，取m=4时有，$$b_2=6$$$$b_3=10$$，$$b_{n+1}=b_n+\left[\frac{ b_n}{3}\right]$$$$(n\ge3)$$

aimisiyou

@kastin   当m=2时有：\(b_{n+1}=b_n+\left[\frac {b_n}{m-1}\right]=b_n+b_n=2b_n\)，公式比较好求。

补充内容 (2015-4-21 10:13):
@kastin   你说的n=10^4是针对m为多少时的情况？我只得出$$b_{n+1}=b_n+[\frac{b_n}{m-1}]$$的一般表达式，对于m=2可以得到$$b_n=2^{n-1}$$.

补充内容 (2015-4-21 10:49):
@kastin    这里的下标n不是总人数N，而是要保证$$\frac{b_n}{m-1}>=N$$时的最小值，如总人数N=100，m=2,则$$b_n=2^{n-1}>=100$$ n最小值取8，此时$$a_n=128$$,故最后出圈的人为$$m*N-b_n=2*100-128=72$$。