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:

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

assuming the first term is $\displaystyle u_1=0$.

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

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

hence

$\displaystyle 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:

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

hence (change of variable)

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

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