How to solve given recurrence relation for a given n and k?

by user3243499   Last Updated July 29, 2018 18:20 PM

Given a recurrence relation as follows:

$$ T(n,k) = \begin{cases} 1, & \text{if $n <= 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) = 2(T(n-1, k))-1

However, this observation does not seem to work for some cases.

How to solve this recurrence relation?



Related Questions


recurrence solution of placing tiles

Updated March 06, 2016 01:08 AM

Combinatorics | Recurrence relations | Problem

Updated May 09, 2017 17:20 PM

Induction for f$(n+2)=f(n+1)+6f(n)$ and its property

Updated August 20, 2017 19:20 PM