# Sequences of sums of Pascal's triangle

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!

• Where do the three sequences come from? (How are you calculating them) – Andrew Szymczak Mar 16 '15 at 17:42
• By definition, I think a more intuitive explicit formula is $a(n) = {n \choose 2} + {n \choose 6} + {n \choose 10} + \ldots = \sum_{k \ge 0} {n \choose 4k-2}$. Note the offset on the OEIS is wrong. With an offset 0 the sequence should start 0,0,1,3,... – Andrew Szymczak Mar 16 '15 at 18:59
• – Lucian Mar 16 '15 at 23:51
• @Lucian: can you please give an example? – user144765 Mar 17 '15 at 7:32

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.

• Thanks for your help! The terms of the second recurrence are: $$0,0,3,21,89,307,977,3031,9321,28479,86505,261615,788969,2375119,7141769,21457999,64439145,193447887,580605705$$ The third one: $$1,7,31,117,439,1729,7063,29201,120471,493617,2008567,8129265,32781847,131886705,529800951,2126056497,8525233303$$ These terms are all I have for now: I generate them using bruteforce so it takes a lot of time. I want to generalize these secuences, i.e. generate any following one. – user144765 Mar 16 '15 at 19:42
• @user144765 What are you brute-forcing? It would help to have some context. – Andrew Szymczak Mar 16 '15 at 19:46
• @user144765 btw, you gave me the first ($g_n$) and second sequence not the second and third. – Andrew Szymczak Mar 16 '15 at 19:50
• About the origin of these sequences - pastebin.com/KH2rRFNU – user144765 Mar 16 '15 at 19:54
• I meant the second and the third ones after the first which is in OEIS. All sequences start with offset one not zero. – user144765 Mar 16 '15 at 20:01

(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$.

• $$G_{e}(2,n): \left\{\left\{a(n)\to \frac{1}{2} \left((-1)^n+1\right) (2 n-1)\right\}\right\}$$ $$G_{e}(3,n): \left\{\left\{a(n)\to \frac{1}{2} \left(2 (-1)^n n^2+3 n^2-2 (-1)^n n-3 n+(-1)^n+1\right)\right\}\right\}$$ $$G_{e}(4,n): \left\{\left\{a(n)\to \frac{1}{12} \left(8 (-1)^n n^3+24 n^3-12 (-1)^n n^2-36 n^2+10 (-1)^n n+24 n-3 (-1)^n-9\right)\right\}\right\}$$ $$G_{e}(5,n): \left\{\left\{a(n)\to \frac{1}{6} (n-1) \left(2 (-1)^n n^3+15 n^3-2 (-1)^n n^2-15 n^2+2 (-1)^n n+15 n-6\right)\right\}\right\}$$ Looks like coefficients in these explicit formulas are binomials... – user144765 Mar 20 '15 at 23:06
• @user144765 ah you beat me to the punch. Just to view the coefficients in a more succinct form $[\alpha_0, \alpha_1, \ldots; \beta_0, \ldots]$ $$1/2 \; [1\;;\; 1] \\ 1/2\; [-1, 2 \;;\; -1, 2] \\ 1/2\;[1, -3, 3 \;;\; 1, -2, 2] \\ 1/12\;[-9, 24, -36, 24 \;;\; -3, 10, -12, 8] \\ 1/6\;[6, -21, 30, -30, 15 \;;\; 0, -2, 4, -4, 2]$$ – Andrew Szymczak Mar 20 '15 at 23:32
• It must relate to binomials. Looks very similar to the explicit formula in the question. That ${-1}^n$s remind me inclusion-exclusion. – user144765 Mar 21 '15 at 0:08
• Hmm that's a good idea. I'll try to think of an IE or an involution. Though I do enjoy the lazy pattern searching method. – Andrew Szymczak Mar 21 '15 at 0:11
• Any integer-valued polynomial is an integer linear combination of binomial coefficients. And ${x \choose 1} = x; {x \choose 2} = \frac{1}{2}x^2-\frac{1}{2}x; {x \choose 3} = \frac{1}{6}x^3-\frac{1}{2}x^2+\frac{1}{3}x; ...$ But that $(-1)^n$s... – user144765 Mar 21 '15 at 20:55