Question

定义在N+上的函数f[x]满足：f[0]=2,f[1]=3,且f[k+1]=3f[k]-2f[k-1]。求：f[n]

Answer 1

解：
f[k+1]=3f[k]-2f[k-1]
f[k+1]-f[k]=2f[k]-2f[k-1]
令A[n]=f[n+1]-f[n]
则：A[n+1]=2A[n]

则：A[0]=f[1]-f[0]=3-2=1
由：A[n+1]=2A[n]
得：
A[1]=2
A[2]=4

....

A[n]=2^n又：
A[n]=f[n+1]-f[n]
A[n-1]=f[n]-f[n-1]
...
A[1]=f[1]-f[0]
相加：
A[n]+A[n-1]+....A[1]=f[n+1]-f[n]+f[n]-f[n-1]+...+f[1]-f[0]
=2^n+2^(n-1)+...+1=f[n+1]-f[0]=f[n+1]-2

所以：2^(n+1)-1=f[n+1]-2

f[n+1]=2^(n+1)+1

即：f[n]=2^n+1

Answer 2

//f[0]=2,f[1]=3,且f[k+1]=3f[k]-2f[k-1]。求：f[n]

#include<stdio.h>
int fun(int n)
{
if (n==0)return 2;
else if (n==1)return 3;
else
return (3*fun(n-1)-2*fun(n-2)); //递归

}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",fun(n));
}