Generate an array of the first M N-Bonacci Numbers

Question

I'm having difficulty understanding the solution this problem:

We are to write a function that generates the first M N-Bonacci numbers. So for example, if N = 2, then this is the sequence of fibonacci numbers {0, 1, 2, 3, 5 ... }. If N = 3, then each element is the sum of the previous 3 numbers, {0, 0, 1, 1, 2, 4, 7, ... }.

According to the solution to this problem, the ith N-Bonacci number, is equal to

nbonacci[i] = nbonacci[i - 1] + nbonacci[i - 1] - nbonacci[i - N - 1]

Can someone please explain how this idea was produced? I know it's a dynamic programming problem, I just don't understand how to come up with this formula on my own. So at a high level, how exactly do you think of this ?

Answer 1

We know that:

BN(i)     = BN(i-1) + BN(i-2) +     ...       + BN(i-N)

That means that

BN(i-1)             = BN(i-2) + BN(i-3) + ... + BN(i-N) + BN(i-N-1)

All I did there was substitute i-i for i in the definition.

In other words (subtracting the last term from both sides of the equality):

BN(i-1) - BN(i-N-1) = BN(i-2) + BN(i-3) + ... + BN(i-N)

Now, I substitute this equation back into the first one. (You can see that the right-hand side of this equality is precisely the trailing part of the first equation, so I can substitute the left-hand side of this equality.)

BN(i)     = BN(i-1) + BN(i-1) - BN(i-N-1) 

That gives you the simplified formula, which can be evaluated without a loop.