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?

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger