Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Question

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach?

My approach: the given series is equal to summation of $\binom{n}{k}$ (here $k$ is from $n/2$ to $n$).

Answer 1

Hint:

This is what you want:

$$\sum_{k=\lfloor n/2\rfloor}^n \binom{n}{k}$$

You can use:

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$

And the fact that

$$\binom{n}{k} = \binom{n}{n-k}$$

Answer 2

HINT:

$$\sum_{i=0}^{2m}\binom{2m}{i}=\sum_{i=0}^{m-1}\binom{2m}{i}+\binom{2m}{m}+\sum_{i=m+1}^{2m}\binom{2m}{i}=\binom{2m}{m}+2\sum_{i=m+1}^{2m}\binom{2m}{i}$$ with $$\sum_{i=0}^{2m}\binom{2m}{i}=(1+1)^{2m}.$$

How about the case for $N=2m-1$?

Answer 3

If you wont a polynomial,
Let $$P(x)=ax^4+bx^3+cx^2+dx+e$$ We can find $a,b,c,d$ and $e$ such that $$P(1)=3$$ $$P(2)=4$$ $$P(3)=11$$ $$P(4)=16$$ $$P(5)=42$$ Then you have a polynomial which can satisfy your sequence. It is better if you can refer the (Lagrange’s) interpolation polynomials.