$$$F_i$$$ is the number of ways to pick at most $$$k$$$ elements from $$$i$$$ elements total.

If you don't pick the first element, you have $$$F_{i-1}$$$ ways to continue.

If you pick the first element, you need to choose at most $$$k-1$$$ from the remaining $$$i-1$$$. This is $$$F_{i-1}$$$ minus the number of ways to pick exactly $$$k$$$ from the remaining $$$i-1$$$ elements, so $$$F_{i-1} - \binom{i-1}{k}$$$.

In total $$$F_{i} = 2F_{i-1} - \binom{i-1}{k}$$$, you can compute the binomials quickly by precomputing factorials.