For example let f(n)=nC0+(n-1)C1+(n-2)C2+(n-3)C3 +…+(n-k)Ck; where k<=n/2;
1<=n<=10^7
How will we solve it ?
I know recusrsive function f(n)=f(n-1)+f(n-2)+1 will solve it .
But i want to general methods to solve this type of questions of converting formulae to recursion.
Here is another problem [Magic Gems][1]. its function is f(n,m)=nC0+(n-(m-1))C1+(n-2*(m-1))C2+(n-3*(m-1))C3+…
Please suggest way to solve above problem
[1]: https://codeforces.com/contest/1117/problem/D