Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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