Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any way to solve the recurrence

$$x[n+1]=(x[n]+1)2^{x[n]+1}-1$$

I know how to solve recurrences with z-transforms, but it doesn't look like that technique will yield anything useful here. I have a feeling I'll be able to work around this if worse comes to worse, but a solution to this recurrence would simplify things greatly.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

First simplify the recurrence by defining $\ y[n]:=x[n]+1\ $ then you want : $$y[n+1]=y[n]\,2^{y[n]}$$ Let's set $\ u[n]:=\log_2(y[n])\ $ to get smaller values then the $\log$ in base $2$ of the last recurrence will give : $$u[n+1]=u[n]+y[n]=u[n]+2^{u[n]}$$ This fast growing sequence appears as sequence A034797 of OEIS (when $a[0]=1$ at least) with reference to this paper 'Sloping Binary Numbers: A New Sequence Related to the Binary Numbers' from Applegate, Cloitre, Deléham and Sloane (see around $(29)$).

Hoping this helped,

share|improve this answer
    
By the looks of things, something is known of the recurrence then, but I don't see a closed form of it anywhere. Looks like it's time to work on that Plan B then. Thanks. –  Mike Dec 6 '12 at 23:44
    
@Mike: you are welcome! –  Raymond Manzoni Dec 7 '12 at 0:00
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.