Sequence generated by polynomial expression

Question

For each, find the polynomial expression that gives $a_n$
1) 1, 6, 17, 34, 57, 86, 121, 162, 209, 262...
2) 4, 4, 10, 28, 64, 24, 214, 340, ...

My attempt of
1) is $3x^2+2x+1$ and
2) is $2x^2+x+4$

Im sure of 1) but cant figure 2) out. Is there any polynomial way of doing it?

Answer 1

Use the Lagrange interpolating polynomial. At (1) it gives you exactly the polynom you already have, but at (2) you get pretty strange polynom, check your data:

$$ $$

Anyway, in your case I would prefer another way to do this. Note that the distance between points is invariant: 1. So you know all $f_1(n) - f_1(n-1) = f_2(n)$. Note that $deg(f_2) < deg(f_1)$, $f_1 \in \int f_2dx$, and you have one point less to calculate $f_2$. Then if you have $f_m$, you can calculate $f_{m-1}$ - jut find the constant by this integral. So you can calculate your $f_1$ as in lazy dynprog, by calculating $f_2$, $f_3$, ... until some $f_m$ is constant (points look like (C, C, C, ..., C))

The common way for this: $$ x_i = x_0 + i\cdot h\\ x_i - x_j = (i-j) \cdot h\\ l_j(x) = \prod \limits_{i=0,i \ne j}^{n} {\frac {x - x_i} {x_j - x_i}}\\ l_j(x) = \frac {\prod \limits_{i=0,i \ne j}^{n} {(x - x_0 - i \cdot h)}} {h^{n-1} \prod \limits_{i=0,i \ne j}^{n} {(j-i)}}\\ $$ Here $L(x) = \sum \limits_{0}^{n} {y_i l_i(x)}$, where $y_i$ are your "$a_n$".

Answer 2

For 1), note that the second difference is a constant = $6$. Thus

$$a_{n+1} - 2 a_n + a_{n-1} = 6$$

The homogeneous solution is $a_n^{(H)} = A n+B$. The inhomogeneous solution should take the form $a_n^{(I)} = C n^2$. Then

$$C[(n+1)^2 + (n-1)^2 - 2 n^2] = 2 C = 6 \implies C=3$$

Noting that $a_1 = 1$ and $a_2 = 2$, I get

$$a_n = 3 n^2 - 4 n + 2$$

I guess we are off by an index, so if I set $n+1 \leftarrow n$, I reproduce your result.

For 2) you can prove that no second-order recurrence characterizes that sequence. You can show this by considering

$$A a_{n+1} + B a_n + C a_{n-1} = 1$$

plugging in $3$ triplets of the sequence, solving for $A$, $B$, and $C$, and then applying that relation to another triplet. You will find that, for the first $3$ triplets, $A=1/10$, $B=-3/10$, and $C=3/10$. So keep trying recurrences of higher order until you get one that consistently satisfies the entire recurrence.

I also proved that no 3rd-order recurrence works as well. Given the numbers you show, there is a unique fourth order recurrence (because we have run out of numbers at this point and do not know the next terms in the sequence). You can find them similarly to how I found the second and 3rd order recurrences. I would not recommend doing these by hand, as it involves inverting a $5 \times 5$ matrix.