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.

Following is the recurrence relation:

a[1] = 1;
a[n_] := a[n - a[n - 1]] + 1
Array[a, 28]

I tried to use RSolve, but it doesn't gives a correct answer.

Clear[a]
RSolve[{a[n] == a[n - a[n - 1]] + 1}, a[n], a]
share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

First, I believe your RSolve syntax is incorrect. I think you want n as the last argument, and you should also have the a[1] == 1 rule:

RSolve[{a[n] == a[n - a[n - 1]] + 1, a[1] == 1}, a[n], n]

This gives a more informative (error?) message:

RSolve::nestdv: The expression a[-1+n] has nested dependent variables. >>

Apparently RSolve doesn't like that.

Second, your recursive function is very inefficient because it lacks memoization. Adding that will make it more practical:

a[1] = 1;
a[n_] := a[n] = a[n - a[n - 1]] + 1

Array[a, 500000] // Timing // First
1.529

Finally, we can work out a function for the nth term manually. Observe that in your sequence each number n repeats n times:

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...

The jump points are therefore triangular numbers:

# (# + 1)/2 & ~Array~ 5
{1, 3, 6, 10, 15}

We can invert this equation with Solve:

Solve[n (n + 1)/2 == x, n]
{{n -> 1/2 (-1 - Sqrt[1 + 8 x])}, {n -> 1/2 (-1 + Sqrt[1 + 8 x])}}

Then pick the correct branch and add Ceiling:

fn[x_] := Ceiling[ (Sqrt[1 + 8 x] - 1)/2 ]

Now:

fn ~Array~ 15
{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}
share|improve this answer
3  
Warning : in Mathematica 8 and later Solve[1/2 n (1 + n) == k, n, Integers] yields the result in terms of ConditionalExpression. You should rather use simply Solve[1/2 n (1 + n) == k, n]. +1. –  Artes Jan 31 '13 at 13:15
    
@Artes Thanks for the correction. –  Mr.Wizard Jan 31 '13 at 13:17
add comment

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.