# Rising Recursion Relationships

Lets say I want to compute the following function in mathematica:

$G[n,k]=G[n+1,k-1] + G[n+2,k-2]$ where I know that $G[n,0]=n$ and $G[n,1]=n^2$.

So, for example, $G[3,2]=G[4,1]+G[5,0]=4^2+5$ or, less trivially,

$G[5,4]=G[6,3]+G[7,2]=(G[7,2]+G[8,1])+(G[8,1]+G[9,0])=((G[8,1]+G[9,0])+G[8,1])+(G[8,1]+G[9,0])= 3G[8,1]+2G[9,0]$

So I attempt it with the following code

RecurrenceTable[{s1[n, k] == s1[n + 1, k - 1] - s1[n + 2, k - 2],
s1[r, 1] == r, s1[r, 0] == r^2}, s1, {n, 2, 6}, {k, 2, 4}] // Grid


However it spits out lots of error messages relating to functions being called with two variables when only one is expected.

-
It is defined via that recursion relationship with those initial conditions? It is the equivalent of $G[n,k]$ in the example. – Benjamin Horowitz Apr 24 '13 at 4:11
Your sample code doesn't spit out any error message here. It just doesn't evaluate to anything. Have you tried restarting the kernel? – halirutan Apr 24 '13 at 4:23
I did, I should mention I am using Mathematica 7, perhaps later editions are smarter... – Benjamin Horowitz Apr 24 '13 at 4:28
Unfortunately, I have only 8.0.4 as oldest version here and I cannot test it in 7. In version 8 are no error messages too. Is it seems, RSolve and RecurrenceTable cannot help you with your problem anyway. – halirutan Apr 24 '13 at 4:34

You can always define the recursive function yourself and use memoizing to speed up computation:

g[n_, 0] := g[n, 0] = n;
g[n_, 1] := g[n, 1] = n^2;
g[n_, k_] := g[n, k] = g[n + 1, k - 1] + g[n + 2, k - 2];

Table[g[n, k], {k, 0, 10}, {n, 0, 10}] // TableForm


-

Note, this can be solved in general form. Start as

RSolve[{G[n, k] == G[n + 1, k - 1] + G[n + 2, k - 2]}, G[n, k], {n, k}]


You have two unknown functions C(1)[x] and C(2)[x] that you can find using your boundary conditions.

A[n_] = C[1][n] /.
Solve[n == (-(1/2) - Sqrt[5]/2)^n C[1][n] + (-(1/2) + Sqrt[5]/2)^
n C[2][n], C[1][n]][[1]]


B[n_] = C[1][1 + n] /.
Solve[n^2 == (-(1/2) - Sqrt[5]/2)^
n C[1][n + 1] + (-(1/2) + Sqrt[5]/2)^n C[2][n + 1],
C[1][n + 1]][[1]]


Combine the two above to find function C(2)[n] - I rename it S2[n]:

S2[n_] = C[2][1 + n] /. Solve[A[n + 1] == B[n], C[2][1 + n]][[1]] /.
n -> n - 1 // FullSimplify


Substitute this in A[n] to find C(1)[n] - I rename it S1[n]

S1[n_] = (-(1/2) - Sqrt[5]/2)^-n (n - (-(1/2) + Sqrt[5]/2)^n S2[n]) //FullSimplify


Finally substitute both in the very original solution to find the final function:

SolvedG[n_, k_] = (-(1/2) - Sqrt[5]/2)^n S1[k + n] + (-(1/2) + Sqrt[5]/2)^
n S2[k + n] // FullSimplify;


So here - you got it - the beauty of math:

SolvedG[n, k] // TraditionalForm


Now verify against @halirutan table - identical !

Table[SolvedG[n, k] // FullSimplify, {k, 0, 10}, {n, 0, 10}] // TableForm


-
Very nice! Why does RSolve have problems when you specify the initial conditions? – halirutan Apr 24 '13 at 5:05
Interesting! I will say though that the actual recursion relation is much more complicated and I know cannot be solved general form (if I could I would totally be flying to Sweden right now to receive my Nobel Prize...) – Benjamin Horowitz Apr 24 '13 at 5:43
No, this is just a simplified version, my actual problem is non-linear in terms of $n$ and $k$. – Benjamin Horowitz Apr 24 '13 at 6:17