2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It is defined via that recursion relationship with those initial conditions? It is the equivalent of $G[n,k]$ in the example. $\endgroup$ Commented Apr 24, 2013 at 4:11
  • $\begingroup$ Your sample code doesn't spit out any error message here. It just doesn't evaluate to anything. Have you tried restarting the kernel? $\endgroup$
    – halirutan
    Commented Apr 24, 2013 at 4:23
  • $\begingroup$ I did, I should mention I am using Mathematica 7, perhaps later editions are smarter... $\endgroup$ Commented Apr 24, 2013 at 4:28
  • $\begingroup$ 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. $\endgroup$
    – halirutan
    Commented Apr 24, 2013 at 4:34

2 Answers 2

5
$\begingroup$

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

enter image description here

$\endgroup$
4
$\begingroup$

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}]

enter image description here

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

Apply your initial conditions G[n,0]:

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]]

Apply your initial conditions G[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

enter image description here

Now verify against @halirutan table - identical !

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

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ Very nice! Why does RSolve have problems when you specify the initial conditions? $\endgroup$
    – halirutan
    Commented Apr 24, 2013 at 5:05
  • $\begingroup$ 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...) $\endgroup$ Commented Apr 24, 2013 at 5:43
  • $\begingroup$ No, this is just a simplified version, my actual problem is non-linear in terms of $n$ and $k$. $\endgroup$ Commented Apr 24, 2013 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.