Finding a formula for the sequence $\{1, 7, 17, 30, 48, 70, 95, 125, \ldots\}$

Question

I have a sequence $$f = \{1, 7, 17, 30, 48, 70, 95, 125, \ldots\}$$

The difference between the entries of f is $$\triangledown f = \{6, 10, 13, 18, 22, 25, 30, \ldots\}$$

Finally, the difference between the entries of $\triangledown f$ is $$\{4, 3, 5, 4, 3, 5, 4, 3, \ldots\}$$ repeating.

I've been trying to find an equation for $f$, but am struggling to piece it together.

Hints would be greatly appreciated, thanks!

Answer 1

You can decompose your problem into 2 simpler ones, and then add solutions.

Second difference, which I will denote by $\Delta^2 f$ is sum of 2 sequences: $$ (4, 3, 5, 4, 3, 5, 4, 3, 5, \ldots) = (4, 4, 4, 4, 4, 4, 4, 4, 4, \ldots) + (0, -1, 1, 0, -1, 1, 0, -1, 1, \ldots) $$ Let $\Delta^2 g = (4, 4, \ldots)$ and $\Delta^2 h = (0, -1, 1, \ldots)$ be such that $f = g + h$. Now solving for general g is easy, we have \begin{align} \Delta g(n) &= 4n + \Delta g(0), \\ g(n) &= 2n(n-1) + n\Delta g(0) + g(0). \end{align} Second one is a bit less standard, but due to being sort of 'balanced', we can easily guess particular solution $$ \begin{array} .\Delta^2 h &&&& 0&& -1&& 1&& 0&& -1&& 1&& 0&& -1&& 1&\ldots\\ \Delta h &&& 0&& 0&& -1&& 0&& 0&& -1&& 0&& 0&& -1&\ldots\\ h && 0&& 0&& 0&& -1&& -1&& -1&& -2&& -2&& -2&\ldots\\ \end{array} $$ So we see that possible $h$ would be $(0, 0, 0, -1, -1, -1, -2, -2, -2, -3, -3, -3, -4, \ldots)$. We have $\Delta f(0) = \Delta g(0) + \Delta h(0) = \Delta g(0)$ and $f(0) = g(0) + h(0) = g(0)$. This gives initial conditions for $g$, and we arrive on $$f(n) = 2n(n-1) + 6n + 1 -\left\lfloor \frac n 3\right\rfloor.$$

Answer 2

Using $1$-based indices, for any integer $n \ge 1$, the entries in $f$ of $f_n$, $f_{n+1}$ and $f_{n+2}$ have first order differences of $f_{n+1}-f_{n}$ and $f_{n+2}-f_{n+1}$, so their second order difference would be

$$(f_{n+2}-f_{n+1}) - (f_{n+1}-f_{n}) = f_{n+2} - 2f_{n+1} + f_{n} \tag{1}\label{eq1A}$$

Thus, if $n = 3k+1$ for some integer $k \ge 0$, from your repeating second order differences, we get

$$f_{n+2} - 2f_{n+1} + f_{n} = 4 \tag{2}\label{eq2A}$$

$$f_{n+3} - 2f_{n+2} + f_{n+1} = 3 \tag{3}\label{eq3A}$$

$$f_{n+4} - 2f_{n+3} + f_{n+2} = 5 \tag{4}\label{eq4A}$$

Adding \eqref{eq2A}, \eqref{eq3A} and \eqref{eq4A} gives

$$\begin{equation}\begin{aligned} f_{n+4} - f_{n+3} - f_{n+1} + f_{n} & = 12 \\ f_{n+4} & = f_{n+3} + f_{n+1} - f_{n} + 12 \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

If $n = 3k+2$ instead, then the RHS of \eqref{eq2A} would $3$, that of \eqref{eq3A} would $5$, and in \eqref{eq4A} would be $4$. Nonetheless, the sum of the RHS would still be $12$, so \eqref{eq5A} is still true. The same thing happens for the $n = 3k + 3$ case. Thus, \eqref{eq5A} applies for all $n \ge 1$.

Note that \eqref{eq5A} is a linear recurrence relation with constant coefficients. Since the $b$ value is $12$ here, it's classified as being nonhomogeneous. The conversion to homogeneous form section explains the conversion process. In particular, we can first try to use

$$y^{*} = \frac{b}{1-a_{1}-\cdots -a_{n}}$$

where the $a_i$ are the coefficients, as long as the denominator is not $0$. Unfortunately, here $a_1 = 1$, $a_2 = 1$, $a_3 = 0$ and $a_4 = -1$ causes the denominator to be $0$. Thus, we need to use its alternate suggestion, in particular applying \eqref{eq5A} with $n$ replaced by $n + 1$ to get

$$f_{n+5} = f_{n+4} + f_{n+2} - f_{n+1} + 12 \tag{6}\label{eq6A}$$

Subtracting \eqref{eq5A} from this results in

$$f_{n+5}= 2f_{n+4} - f_{n+3} + f_{n+2} - 2f_{n+1} + f_{n} \tag{7}\label{eq7A}$$

This is now in homogenous form, so we can solve this using the general solution method. In particular, we first need to find the roots of the characteristic polynomial, with this being

$$\lambda^5 = 2\lambda^4 - \lambda^3 + \lambda^2 - 2\lambda + 1 \tag{8}\label{eq8A}$$

Fortunately, there's one fairly obvious root of $\lambda = 1$. Factoring this out, and then also several other factors, we get

$$\begin{equation}\begin{aligned} 0 & = (\lambda - 1)(-\lambda^4 + \lambda^3 + \lambda - 1) \\ & = (\lambda - 1)(-\lambda^3(\lambda - 1) + (\lambda - 1)) \\ & = (\lambda - 1)^2(-1)(\lambda^3 - 1) \\ & = (-1)(\lambda - 1)^3(\lambda^2 + \lambda + 1) \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

The roots of $\lambda^2 + \lambda + 1$ are $\lambda = \frac{-1\pm\sqrt{3}i}{2}$, i.e., they're complex. The Wikipedia article explains how to finish determining the solution, which I'm leaving to anybody interested.