Upper bounds for Stern's diatomic sequence and related sequences (Q727176)

Summary: Let \((s_2(n))_{n=0}^\infty\) denote Stern's diatomic sequence. For \(n\geqslant 2\), we may view \(s_2(n)\) as the number of partitions of \(n-1\) into powers of \(2\) with each part occurring at most twice. More generally, for integers \(b,n\geqslant 2\), let \(s_b(n)\) denote the number of partitions of \(n-1\) into powers of \(b\) with each part occurring at most \(b\) times. Using this combinatorial interpretation of the sequences \(s_b(n)\), we use the transfer-matrix method to develop a means of calculating \(s_b(n)\) for certain values of \(n\). This then allows us to derive upper bounds for \(s_b(n)\) for certain values of \(n\). In the special case \(b=2\), our bounds improve upon the current upper bounds for the Stern sequence. In addition, we are able to prove that \(\limsup_{n\rightarrow\infty}\frac{s_{b}(n)}{n^{\log_{b}\phi}}=\frac{(b^{2}-1)^{\log_{b}\phi}}{\sqrt{5}}\).