0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Where do the three sequences come from? (How are you calculating them) $\endgroup$ – Andrew Szymczak Mar 16 '15 at 17:42
  • $\begingroup$ 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,... $\endgroup$ – Andrew Szymczak Mar 16 '15 at 18:59
  • $\begingroup$ See Gosper's algorithm and Wilf-Zeilberger pair. $\endgroup$ – Lucian Mar 16 '15 at 23:51
  • $\begingroup$ @Lucian: can you please give an example? $\endgroup$ – user144765 Mar 17 '15 at 7:32
1
$\begingroup$

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 $ enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user144765 Mar 16 '15 at 19:42
  • $\begingroup$ @user144765 What are you brute-forcing? It would help to have some context. $\endgroup$ – Andrew Szymczak Mar 16 '15 at 19:46
  • $\begingroup$ @user144765 btw, you gave me the first ($g_n$) and second sequence not the second and third. $\endgroup$ – Andrew Szymczak Mar 16 '15 at 19:50
  • $\begingroup$ About the origin of these sequences - pastebin.com/KH2rRFNU $\endgroup$ – user144765 Mar 16 '15 at 19:54
  • $\begingroup$ I meant the second and the third ones after the first which is in OEIS. All sequences start with offset one not zero. $\endgroup$ – user144765 Mar 16 '15 at 20:01
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $$ 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... $\endgroup$ – user144765 Mar 20 '15 at 23:06
  • $\begingroup$ @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] $$ $\endgroup$ – Andrew Szymczak Mar 20 '15 at 23:32
  • $\begingroup$ It must relate to binomials. Looks very similar to the explicit formula in the question. That ${-1}^n$s remind me inclusion-exclusion. $\endgroup$ – user144765 Mar 21 '15 at 0:08
  • $\begingroup$ 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. $\endgroup$ – Andrew Szymczak Mar 21 '15 at 0:11
  • $\begingroup$ 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... $\endgroup$ – user144765 Mar 21 '15 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.