求递归方程：1、f(n)=-2f(n-1)+2^n-n^2，f(0)=1;2、f(n)=nf(n-1)+2^n-n^2，f(0)=3.
- 如何用生成函数求解递归方程f(n)=2f(n/2)+cn
- 求解递归方程：(1) f(1)=1;f(n)=2*f(n-1)+1;
- 求高手，解递归方程： 已知： f(n) = -2f(n-1)+2^n-n^2 f(0) = 1; 求：f(n)
- 解递归方程 f(n) =5 f(n-1)-6f(n-2), n>2; f(0)=1, f(1)=0.
如何用生成函数求解递归方程f(n)=2f(n/2)+cn
^解：
令f(1)=c
f(2)=2c+2
f(4)=2(2c+2)+4 = 4c+8
f(8) = 2(4c+8)+8 = 8c+24
f(16) = 2(8c+24)+16 = 16c+64
f(2^k) = c*2^k + P(k)
考虑P(k)
P(0) = 0
P(1) = 2 *P(0) + 2
P(2) = 2*P(1)+4
p(n-2) = 2*P(n-3)+2^(n-2)
p(n-1) = 2*P(n-2)+2^(n-1)P(n)
= 2* P(n-1) + 2^n = 2*2*P(n-2)+2*2^(n-1)+2^n
= 4P(n-2)+2*2^n
= 4*2P(n-3)+4*2^(n-2)+2*2^n
归纳得到P(n) = 2^kP(n-k)+k*2^n = 2^nP(n-n)+n*2^n =n*2^n
所以P(n-1) = (n-1)2^(n-1)
2*P(n-1)+2^n = 2*(n-1)*2^(n-1) + 2^n=P(n) 得到验证
带回f(2^k)得到f(2^k) = c*2^k+k*2^k，对于任意常数c成立
扩展资料
性质：
1、 子问题须与原始问题为同样的事，且更为简单。
2、不能无限制地调用本身，须有个出口，化简为非递归状况处理。
3、由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
4、递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
求解递归方程：(1) f(1)=1;f(n)=2*f(n-1)+1;
f(1)=1;
f(n)=2*f(n-1)+1
f(n-1)=2*f(n-2)+1 (1)
f(n-2)=2*f(n-3)+1 (2)
.....
f(2)=2f(1)+1 (n-2)
f(1)=1 (n-1)
(1)x2+(2)x4+....+(n-2)x2^(n-2)+(n-1)x2^(n-1)消去相同的得
f(n)=1+2+2^2+....+2^(n-1)
f(n)=2^n-1
求高手，解递归方程： 已知： f(n) = -2f(n-1)+2^n-n^2 f(0) = 1; 求：f(n)
1.记g(n)=f(n)-(1/2)*(2^n)+(n^2)/3+4n/9+2/27,
g(n)=-2g(n-1)
然后解g(n)通项，再算f(n).
解递归方程 f(n) =5 f(n-1)-6f(n-2), n>2; f(0)=1, f(1)=0.
特征方程 x²=5x-6，解为 x1=2，x2=3，
因此 f(n)=a*2ⁿ+b*3ⁿ，
由初始条件得 a+b=1，2a+3b=0，
解得 a=3，b=-2，
因此 f(n)=3*2ⁿ - 2*3ⁿ 。