求通项公式
已知a0=2,an+1=an+n/2],求an=? ([]为取整函数，如=2,=5)补充内容 (2015-4-20 23:17):
刚开始学编辑数学公式，为了美观再写一下。\(b_2=4,\;b_{n+1}=b_n+\left[\frac{b_n}{2}\right]\),求 \(b_n\) 这道题，基本就是对着
http://spaces.ac.cn/index.php/archives/3064/
抄一次。原始来源是@kastin 大神
http://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=5794&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\)是上取整函数。 把通项公式改为
$$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+\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 于 2015-4-20 13:03 编辑
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的上限吗？ aimisiyou 发表于 2015-4-20 12:34
比如说采用这种近似公式，$$a_1-a_2-a_3……a_n$$都正确,但从$$a_{n+1}$$开始不准确了，能判断n的上限 ...
这不是近似，原则上来说，可以算出$\beta$的无穷位小数，而对于精确的$\beta$，这个公式对于所有$n$都成立 282842712474 发表于 2015-4-20 13:00
这不是近似，原则上来说，可以算出$\beta$的无穷位小数，而对于精确的$\beta$，这个公式对于所有$n$都 ...
不可能进行无穷位数运算吧，
如果系数保留五位小数公式准确到\(a_n\), \(n\) 最大为多少？
如果系数保留六位小数公式准确到\(a_m\),\(m\)最大为多少？ aimisiyou 发表于 2015-4-20 14:04
不可能进行无穷位数运算吧，如果系数保留五位小数公式准确到$$a_n$$,n最大为多少？如果系数保留六位小数 ...
为什么不行？计算足够多的a_n就能够计算足够多的位数。当然，这涉及到一个循环论证的问题。但是，这个系数确实是精确存在的，我们能不能计算出它来，只是我们的能力问题。
假设发现β正好等于自然对数的底e，那么你觉得这个答案是不是精确的？
当然，你思考的问题(精确度跟有效的n)也有一定的意义，但我觉得没多大必要。 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\)时的情况，运行效率对比递归方法有很大提高！ 往前进一步，取m=4时有，$$b_2=6$$$$b_3=10$$，$$b_{n+1}=b_n+\left[\frac{ b_n}{3}\right]$$$$(n\ge3)$$ @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$$。
页:
[1]
2