Proof of a conjecture of Stanley about Stern's array

Abstract

Stanley, building on work of Stern, defined an array of numbers by the recurrence $s(n,2k)=s(n-1,k)$, $s(n,2k+1)=s(n-1,k)+s(n-1,k+1)$. Stanley showed that, for each positive integer $r$, the sequence $s_n^r:={\sum }_{k}s(n,k{)}^r$ obeys a homogeneous linear recurrence in $n$ of length $r/2+O(1)$. Numerical evidence, however, suggested that $s_n^r$ obeys shorter recurrences, of length $r/3+O(1)$. We prove Stanley's conjecture.

Cited by in corpus (1)

• The Rank-Generating Functions of Upho Posets