How to solve given recurrence relation for a given n and k? Given a recurrence relation as follows:
$$
T(n,k) = \begin{cases}
1,  & \text{if $n \leq k$} \\
T(n-1,k) + T(n-2,k) +... + T(n-k,k) & \text{otherwise}
\end{cases}
$$
Find $T(n,k)$.
Link to question: https://www.codechef.com/problems/KFIB
As the answer can be big, I have to find it
My observation is: $T(n, k) = 2T(n-1, k)-1$.
However, this observation does not seem to work for some cases.
How to solve this recurrence relation?
 A: Your observation is the key, although you have it wrong. It should be $$T_{n+1,k}=2T_{n,k}-T_{n-k,k}.$$
for $n>k$. The $n>k$ condition is important, as it is used for using the definition of $T_{n,k}$ and $T_{n+1,k}$. This allows you to reformulate the original recursion, which is indeed what the other answers did. Eventually we can rewrite the recurrence as
$$
T_{n,k} =
\begin{cases}
1  & n < k+1 \\
k  & n = k+1 \\
2T_{n-1,k}-T_{n-1-k,k} & n > k+1
\end{cases}
$$
(we have only shifted indices from $n+1$ to $n$ and dealt with special case $n=k+1$ on its own). 
Then there are few further optimizations you can do, such as (not limited to):


*

*using dynamic programming and basically storing the intermediate results. 

*starting from $1$ and calculating the values with increasing $n$ (as opposed to starting from desired $n$ and calling the function recursively). So you would avoid actual function recursion by storing last $k$ values, and updating the values continually. This automatically also satisfies the first bullet by storing last $k$ values.

*calculating modulo along the way at each step, since that will keep the numbers small and avoids overflow
Of course you could also calculate a closed form solution of this new recurrence, but it won't be of much practical use, since the numbers will be too big and you will be operating in floating point arithmetic (unless you are using computer algebra system), so the number would overflow quickly (you wouldn't be able to decrease the number by modulo in intermediate steps, since you would directly calculate the final, large value).
