Thread: Determining the formula of this sequence?

1. Determining the formula of this sequence?

I was given the sequence
0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
and I'm looking for a method to determine an explicit formula for this.
I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

Anyone know a way to figure this out?

2. Originally Posted by paupsers
I was given the sequence
0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
and I'm looking for a method to determine an explicit formula for this.
I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

Anyone know a way to figure this out?
Good idea to look at differences. So you found:

$(u_{n+2}-u_{n+1})-(u_{n+1}-u_n)=2^n$,

assuming the first term is $u_1=0$.

If you sum the above equalities for $n$ ranging from 1 to $n$, you get a telescoping sum on the left, and a geometric sum on the right, which leads to:

$(u_{n+2}-u_{n+1})-(u_2-u_1)=2+2^2+\cdots +2^n = 2^{n+1}-2$,

hence

$u_{n+2}-u_{n+1}=2^{n+1}-1$.

Summing again this latter equality we have again a telescoping sum on the left and a geometric sum (minus constant terms) on the right, and we get:

$u_{n+2}-u_2=(2^2-1)+\cdots+(2^{n+1}-1)$,

hence (change of variable)

$u_n = (2^2-1)+\cdots +(2^{n-1}-1)+1$

and finally $u_n=2^n-n-1$. Same method works in many situations.

3. Originally Posted by paupsers
I was given the sequence
0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
and I'm looking for a method to determine an explicit formula for this.
I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

Anyone know a way to figure this out?
The Encyclopaedia of Integer Sequences gives: $2^n-n-1$

CB

4. Hello, paupsers!

Given the sequence: . $0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, \hdots$

I'm looking for a method to determine an explicit formula for this.
I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.
This is true . . . and should give you a big hint.
Consider the general form: . $f(n) = 2^n$

How does it compare with the given sequence?

$\begin{array}{c|cccccccccc}\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
\text{Sequence:} & 0 & 1 & 4 & 11 & 26 & 57 & 120 & 247 & 502 & 1013 \\ \hline
f(n) = 2^n & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 \\ \hline
\text{Error:} & +2 & +3 & +4 & +5 & +6 & +7 & +8 & +9 & +10 & +11\\ \hline
\end{array}$

If we use $f(n) = 2^n$, each term is too large by $(n+1)$

Therefore, the explicit formula is: . $F(n) \;=\;2^n - (n+1)$