2
$\begingroup$

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.

1 Answers 1

3

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,

  • 0
    @Mike: you are welcome!2012-12-07