Problem 940

[KING-OLE]

I am not sure I understand the SUM from i=2 to k.

In the example S(3), how is 3 used to only look at (1,1) (1,2) (2,1) (2,2) ?

[oivortex2]

The sum is evaluated over pairs (f_i, f_j) of Fibonacci numbers. The example S(3) is like that because f_2 = 1 and f_3 = 2.

[KING-OLE]

Thanks. I missed that.

Now I just have to figure out why my S(5) gives me 10,407 instead of 10,396.

[KING-OLE]

I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

Yes?

[DJohn]

I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

That is not correct. A(0, n) is undefined if n is not 0 or 1. You can't assume any value for it. If you need it to be zero, you've probably gone wrong somewhere.

[KING-OLE]

So, how would you find A(1,3)?

Using first formula: A(1,3) = A(0,4) + A(0,3). Both A(0,4) and A(0,3) are unspecified.

Using second one: A(1,3) = 2A(1,2) + A(0,2). A(0,2) is unspecified.

What am I missing?

[pjt33]

I presume A(0,j) where j>1 = 0 as there's no way of finding those values.

That is not correct. A(0, n) is undefined if n is not 0 or 1.

"Undefined" is not the correct word to use. It's perfectly well defined, but to determine the value it's necessary to make suitable application of the recurrence relations.

So, how would you find A(1,3)?

Build it up bit by bit. Try expanding the recurrence relations for small values of m and n, and then see which ones relate one unknown and two knowns. Then check again to see what you can do with the new known.