1
$\begingroup$

Let $$P_n(x) = \sum_{k=0}^{\lfloor n/2\rfloor} x^k\binom{n-k}{k}.$$ It's known that $P_n(1) = F_{n+1}$, the $(n+1)$th Fibonacci number, see for example here. Can we find a closed form for this polynomial? This would allow to find other similar sums of this form by using derivatives/integrals.

Edit:

As per suggestions in the comments: $$P_{n+2}(x) = P_{n+1}(x) +xP_n(x),\ P_0(x) = P_1(0) = 1$$

Let $y^2 = y+x$ so that $y_{\pm} = \frac{1\pm\sqrt{1+4x}}{2}$, then $P_n(x) = Ay_+^n+By_-^n$ $$\begin{cases} A+B = 1 \\ Ay_++By_- = 1\end{cases}$$ so that $B = 1-A$ and $A = \frac{1-y_-}{y_+-y_-}$.

So $P_n(x) = \frac{1-y_-}{y_+-y_-}y_+^n + \frac{y_+-1}{y_+-y_-}y_-^n$ is a closed formula for $P_n(x)$. That is, $$P_n(x) = \frac{1}{\sqrt{1+4x}}\left( \left(\frac{1+\sqrt{1+4x}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{1+4x}}{2}\right)^{n+1}\right).$$

And indeed for $x = 1$ we get the Binet formula.

$\endgroup$
4
  • 2
    $\begingroup$ Did you try to immitate the proof for the result of Fibonacci numbers and find a reccurence formula for arbitrary $x$? $\endgroup$
    – donaastor
    Commented Jun 26, 2023 at 14:15
  • 2
    $\begingroup$ ... and then use a generalization of the Binet formula to get a closed form. $\endgroup$
    – Robert Israel
    Commented Jun 26, 2023 at 14:22
  • $\begingroup$ Sorry for this easy question, I just didn't realize it was this simple. $\endgroup$
    – Jakobian
    Commented Jun 26, 2023 at 14:39
  • $\begingroup$ If we think of Fibonacci numbers as counting compositions of $n$ into parts of size $1$ and $2$, then $x$ in the formula for $P_n(x)$ marks the $2$'s. Thus, the ordinary generating function of $P_n(x)$ (say, in $y$) is $\frac{1}{1-y-xy^2}$. Finding the partial fractions expansion etc. as for $F_n$ yields your formula. $\endgroup$
    – Alexander Burstein
    Commented Jun 26, 2023 at 16:16

0

Reset to default

You must log in to answer this question.