Ways to choose k non-consecutive integers from n consecutive integers.

let f(n, k) be the # of ways of choosing k integers without replacement from
n consecutive integers so that no two selected are consecutive.
a. give a recurrence for f(n, k)
b. efficient implementation of f(n, k)


Recurrence:
f(n,0) = 0;
f(n,1) = n;
f(n,n) = 1;
f(n,k) = f(n-1, k) + f(n-2, k-1);


OR
f(n,k) = f(n-2, k-1) + f(n-3, k-1) ... f(2(k-1)-1, k-1);


Sample output(s):
n=4, k=2;
n: 4
k: 2
result: 3


n=5, k=3;
n: 5
k: 3
result: 1