Determining the formula of this sequence?

**paupsers** · October 19th 2009, 01:01 PM

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?

**Laurent** · October 19th 2009, 01:50 PM

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.

**CaptainBlack** · October 19th 2009, 02:31 PM

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

**Soroban** · October 20th 2009, 08:27 PM

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)$

Thread: Determining the formula of this sequence?

LinkBack

Thread Tools

Display

Determining the formula of this sequence?

Similar Math Help Forum Discussions

Determining Formula for a graph

determining formula for sequences.

sequence formula

Geometric Sequence, Determining common ratio.

Help on determining a probability formula

Search Tags