# 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).

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?

Tags :