大师作文网母函数和递归问题计算如图递归函数的的母函数,然后确定其an项的渐进特性
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/11 16:16:00
母函数和递归问题
计算如图递归函数的的母函数,然后确定其an项的渐进特性
计算如图递归函数的的母函数,然后确定其an项的渐进特性
a(n+1)=2a(n)+n①
a(n)=2a(n-1)+n-1②
①-②,得a(n+1)-a(n)=2a(n)-2a(n-1)+1,
该式两侧同时加1,得a(n+1)-a(n)+1=2[a(n)-a(n-1)+1]
所以 a(n+1)-a(n)+1是以2为公比的等比数列
a(1)-a(0)+1=2
a(2)-a(1)+1=2*2=2^2
……
a(n+1)-a(n)+1=2^(n+1)
a(n+1)+S(n)-a(0)-S(n)+n+1=2+2^2+……+2^(n+1)
a(n+1)=2^(n+2)-n-2
所以 a(n)=2^(n+1)-n-1
a(n)=2a(n-1)+n-1②
①-②,得a(n+1)-a(n)=2a(n)-2a(n-1)+1,
该式两侧同时加1,得a(n+1)-a(n)+1=2[a(n)-a(n-1)+1]
所以 a(n+1)-a(n)+1是以2为公比的等比数列
a(1)-a(0)+1=2
a(2)-a(1)+1=2*2=2^2
……
a(n+1)-a(n)+1=2^(n+1)
a(n+1)+S(n)-a(0)-S(n)+n+1=2+2^2+……+2^(n+1)
a(n+1)=2^(n+2)-n-2
所以 a(n)=2^(n+1)-n-1