Sequences of sums of Pascal's triangle

Question

The sequence $$ 1,3,6,10,16,28,56,120,256,528,1056 $$ is defined in OEIS as "sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 2"". It satisfies the recurrence $$ a(n) = 4a(n-1)-6a(n-2)+4a(n-3) $$ and can be explicitly calculated as $$ \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}{n+1 \choose 2k}\frac{1-(-1)^k}{2} $$

I suspect that following sequences $$ 0,0,3,21,89,307,977,3031,9321,28479,86505,261615,788969,2375119 $$ $$ 1,7,31,117,439,1729,7063,29201,120471,493617,2008567,8129265 $$ $$ 0,0,10,122,906,5478,30274,160974,840602,4343142,22270674 $$ also relate to sums of terms in Pascal's triangle but can't figure it out. For example, the first of above-mentioned sequences has minimal characteristic polynomial $$ x^6 - 8x^5 + 27x^4 - 54x^3 + 70x^2 - 56x + 24 $$

Can any relation with Pascal's triangle can be established for that sequences?

Thanks!

Answer 1

If you want to relate a sequence to Pascal's triangle, it's usually a good idea to write out the sequence in the basis of binomial coefficients. We can do this by computing the difference table. Suppose we have a sequence $h_n$, then our difference table is computed

$\qquad \qquad \qquad \qquad \qquad \qquad \quad $

where $\Delta h_n = h_{n+1} - h_n$. In such a table, the 0th diagonal $h_0, \Delta h_0, \Delta^2 h_0, \ldots =: c_0, c_1, c_2, \ldots$ gives us our sequence in terms of the binomial coefficients.

$$ h_n = c_0 {n \choose 0} + c_1 {n \choose 1} + c_2 {n \choose 2} + \ldots $$

Let's look at the difference table for your first sequence $g_n$

$$ \tiny \begin{array} {cccccccccccccccccccccccccccccc} \\ 0 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 0 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 3 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 21 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 89 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 307 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 977 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 3031 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 9321 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 28479 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 86505 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 261615 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 788969 \\ & 0 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 3 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 18 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 68 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 218 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 670 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 2054 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 6290 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 19158 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 58026 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 175110 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 527354 \\ && 3 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 15 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 50 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 150 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 452 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 1384 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 4236 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 12868 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 38868 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 117084 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 352244 \\ &&& 12 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 35 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 100 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 302 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 932 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 2852 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 8632 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 26000 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 78216 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 235160 \\ &&&& 23 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 65 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 202 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 630 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 1920 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 5780 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 17368 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 52216 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 156944 \\ &&&&& 42 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 137 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 428 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 1290 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 3860 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 11588 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 34848 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 104728 \\ &&&&&& 95 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 291 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 862 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 2570 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 7728 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 23260 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 69880 \\ &&&&&&& 196 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 571 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 1708 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 5158 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 15532 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 46620 \\ &&&&&&&& 375 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 1137 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 3450 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 10374 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 31088 \\ &&&&&&&&& 762 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 2313 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 6924 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 20714 \\ &&&&&&&&&& 1551 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 4611 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 13790 \\ &&&&&&&&&&& 3060 \!\!\!\!\!\!\! && \!\!\!\!\!\!\! 9179 \\ &&&&&&&&&&&& 6119 & \ldots \\ \end{array} $$

The zeroth diagonal is $\boldsymbol{c} = [0, 0, 3, 12, 23, 42, 95, 196, 375, 762, 1551, 3060, 6119]$, meaning $g_n = 3 {n \choose 2} + 12 {n \choose 3} + \ldots$. It turns out that there is a linear dependence of the terms $c_k$

$$ c_k = 2c_{k-1} - 2c_{k-2} + 6c_{k-3} - 5c_{k-4} + 4c_{k-5} - 4c_{k-6} $$

So $g_n$ is the inner product of the linear recurrence $\boldsymbol{c}$ and the $n$th row of Pascal's triangle. I don't think we can do much better than that. Unfortunately, the other two sequences don't have enough terms to extrapolate any relation.

Answer 2

(Too long for a comment, let's continue the chat under this post so we can view equations). I was trying to do that in the chatroom, to no avail. And you still need the initial values. The characteristic polynomial uniquely specifies the recurrence, not the sequence. Btw, I think it's better to use the $\bullet$ for the index being held fixed. So $G_{e}(\bullet,H)$ is the sequence $G_e(W,1), G_e(W,2), \ldots$, and it has characteristic polynomial $(x^2-1)^W$. Thus, the general solution is of the form $$G_e(W,H) = \sum_{k=0}^{W-1} (\alpha_k + (-1)^H \beta_k) \, H^k $$ So you need to find constants $\alpha_k$ and $\beta_k$ that satisfy the initial conditions. To make this a little easier we can decouple the sequence into two independent ones; let $G_{e}'$ denote every odd term of the sequence and $G_{e}''$ denote every even term. That is, $G_{e}'(\bullet,h) = G_{e}(\bullet,2h-1)$ and $G_e''(\bullet,h) = G_e(\bullet,2h)$. Then both $G_e'$ and $G_e''$ have characteristic polynomial $(x-1)^W$. This means that the general solution of each of these will be of the form

$$ \sum_{k=0}^{W-1} \alpha_k \, H^k $$

In chat I found the first few of these $$ \begin{array}{ll} G_e'(1,h) &= 0 \\ G_e''(1,h) &= 1 \\ G_e'(2,h) &= 0 \\ G_e''(2,h) &= 2h+1 \\ G_e'(3,h) &= 1 - 3h + 2h^2 \\ G_e''(3,h) &= 25 - 35h + 10h^2 \\ G_e'(4,h) &= -5 + (55/3)h - 24h^2 + 32h^3 \\ G_e''(4,h) &= -1 + (17/3)h - 16h^2 + (64/3)h^3 \\ \end{array} $$ They don't seem to follow any sort of pattern. You might try to find a pattern in the full sequence $G_e$.