Finding recurrence relation from combinatorics formulas

codeforces
combinatorics
medium
recursion

#1

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


#2

click