I've been playing around with an open problem I found in Peter Winkler's puzzle book. Roughly, it is
Let $C_p(n)$ be the expected length of the longest common subsequence of two random coin flip sequences of length $n$, with a coin that gives heads with probability $0<p<1$. Let $C_p=\lim_{n\to\infty}C_p(n)/n$. Compute $C_{1/2}$, or at least prove $C_p$ is minimized when $p=1/2$.
I'm attempting to compute $C_{1/2}$. Using some fishy recursive stuff, I've essentially reduced it to computing $\sum_{k=2}^{n-1}F_n^{(k)}$ or at least $\lim_{n\to\infty}\frac{1}{2^n}\sum_{k=2}^{n-1}F_n^{(k)}$, where $F_n^{(k)}$ is the $n$th term of the $k$-nacci sequence, see https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Higher_orders. I've wondered if anyone has studied this sum in the past or if there are any conjectures involving it.
The sequence $S_n=\sum_{k=2}^{n-1}F_n^{(k)}$ is closely related to
A048888on OEIS. In fact $\lim\limits_{n\to\infty}S_n/2^n=0$.A more subtle result is the asymptotics $S_n\asymp(2^{n+1}/n)f(\log_2 n)$, where $$f(x)=\sum_{m\in\mathbb{Z}}2^{m+x}e^{-2^{m+x}}=\frac1{\log2}\sum_{m\in\mathbb{Z}}\Gamma\left(1+\frac{2m\pi i}{\log 2}\right)e^{-2mx\pi i}$$ is an $1$-periodic function oscillating around $1/\log2$ with very small amplitude. The asymptotics is understood in the following sense: let $A_n=nS_n/2^{n+1}$; then $\lim\limits_{n\to\infty}A_{2^n r}=f(\log_2 r)$.
Here are sketchy ideas towards a proof of this result. It is known that $F_n^{(k)}$ is the closest integer to $c_k r_k^{n+1-k}$, where $r_k\in(1,2)$ satisfies $r_k+r_k^{-k}=2$, and $c_k=(r_k-1)/[(k+1)r_k-2k]$ (in fact, a weaker estimate of $|F_n^{(k)}-c_k r_k^{n+1-k}|$ would suffice). It is also known that, as $k\to\infty$, $$r_k=2-2^{-k}-O(k\cdot2^{-2k}),\qquad c_k=\frac12+O(k\cdot 2^{-k})$$ (in fact, there are convergent series of this type for $r_k$ and $c_k$). Then it's not hard to show that we can replace $F_n^{(k)}$ by $(2-2^{-k})^{n+1-k}/2$ in the expression for $A_n$, as $n\to\infty$: \begin{align} A_n&=\frac{n}{2^{n+1}}\sum_{k=2}^{n-1}\frac12(2-2^{-k})^{n+1-k}+o(1) \\&=n\sum_{k=3}^n 2^{-k}(1-2^{-k})^{n+2-k}+o(1) \\\implies A_{2^n r}&=2^n r\sum_{k=3}^{2^n r} 2^{-k}(1-2^{-k})^{2^n r+2-k}+o(1) \\\color{gray}{[k=n-m]}\quad&=\sum_{m=n-2^n r}^{n-3}(2^m r)(1-2^{m-n})^{2^n r+2+m-n}+o(1) \\\underset{n\to\infty}{\longrightarrow}&\phantom{=}\sum_{m=-\infty}^\infty(2^m r)e^{-2^m r}=f(\log_2 r) \end{align} where the limit is taken termwise, using "the discrete DCT" (aka Tannery's theorem).