An Identity for a Fibbonacci-Type Polynomial

Question

Problem:

The polynomials $p_{n}\left(x\right)$ are defined recursively by the linear homogenous order 2 difference equation $$p_{n+1}\left(x\right)=2\left(1-2x\right)p_{n}\left(x\right)-p_{n-1}\left(x\right)$$ and the initial conditions $p_{0}\left(x\right)=0$ and $p_{1}\left(x\right)=1$, for any $n \in \mathbb{N}$ and any number $x$ in a field not of characteristic 2.

Show that $$p_{n+1}\left(x\right)+p_{n}\left(x\right)=\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n-i}x^{i}}$$

*Please note: I would like to avoid using the following in the solution of the problem: trigonometric functions, chebyshev polynomials, analysis, generating functions, complex numbers. I would like to find an algebraic or combinatorial proof, but could settle for an induction/recursion solution.

My work so far:

I found that there are a few ways to go about it, but the following seems the simplest.

Denote $1-x \equiv a$ and $x \equiv b$ and obtain $a+b=1$. Using this notation we will rewrite the above difference equation as $$p_{n+1}\left(x\right)=2\left(a-b\right)p_{n}\left(x\right)-\left(a+b\right)p_{n-1}\left(x\right)$$ and by using it iteratively obtain $$p_{n+1}\left(x\right)+p_{n}\left(x\right)=\left(3a-b\right)\left(p_{n}\left(x\right)+p_{n-1}\left(x\right)\right)-\left(2\right)\left((2a)p_{n-1}\left(x\right)\right)=\left(5a^2-10ab+b^2\right)\left(p_{n-1}\left(x\right)+p_{n-2}\left(x\right)\right)-\left(4a-4b\right)\left((2a)p_{n-2}\left(x\right)\right)=\left(7a^3-35a^{2}b+21ab^2-b^3\right)\left(p_{n-2}\left(x\right)+p_{n-3}\left(x\right)\right)-\left(6a^2-20ab+6b^2\right)\left((2a)p_{n-3}\left(x\right)\right)=\left(9a^4-84a^{3}b+126a^{2}b^2-36ab^3+b^4\right)\left(p_{n-3}\left(x\right)+p_{n-4}\left(x\right)\right)-\left(8a^3-56a^{2}b+56ab^2-8b^3\right)\left((2a)p_{n-4}\left(x\right)\right)$$ ...and so on. From the above I give the following guess for $1 \leq k \leq n$ $$p_{n+1}\left(x\right)+p_{n}\left(x\right)=\left(\sum_{i=0}^{k}{\left( -1\right)^{i}\binom{2k+1}{2i+1}\left(1-x\right)^{k-i}x^{i}}\right)\left(p_{n-k+1}\left(x\right)+p_{n-k}\left(x\right)\right)-\left(\sum_{i=0}^{k-1}{\left( -1\right)^{i}\binom{2k}{2i+1}\left(1-x\right)^{k-1-i}x^{i}}\right)\left((2a)p_{n-k}\left(x\right)\right)$$ so for $k=n$ we should obtain what we want to show. I may just have some mental block, but I wasn't able to formulate an inductive/recursive argument to prove this. My wish is to find an algebraic or combinatorial proof, but formaluting an inductive/recursive argument should be a good start.

Answer 1

Here is another answer that should meet the OP requirements, but it is quite lengthy.

\begin{align*} \text{Let }q_n&=\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n-i}x^{i}} \\ \text{and }a_n&=\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i}\left(1-x\right)^{n-i}x^{i}} \\ q_{n+1}&=\sum_{i=0}^{n+1}{\left( -1\right)^{i}\binom{2n+3}{2i+1}\left(1-x\right)^{n+1-i}x^{i}} \\ \text{but } \binom{2n+3}{2i+1}&= \binom{2n+1}{2i+1}+2\binom{2n+1}{2i}+\binom{2n+1}{2i-1}\\ \text{then } q_{n+1}&=\sum_{i=0}^{n+1}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n+1-i}x^{i}} + \sum_{i=0}^{n+1}{\left( -1\right)^{i}\binom{2n+1}{2i-1}\left(1-x\right)^{n+1-i}x^{i}}\\ &+2 \sum_{i=0}^{n+1}{\left( -1\right)^{i}\binom{2n+1}{2i}\left(1-x\right)^{n+1-i}x^{i}}\\ &=(1-x)\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n-i}x^{i}} - x\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n-i}x^{i}}\\ &+2 \sum_{i=0}^{n+1}{\left( -1\right)^{i}\binom{2n+1}{2i}\left(1-x\right)^{n+1-i}x^{i}}\\ q_{n+1}&=(1-2x)q_n+ 2(1-x)a_n\\ \ \\ \color{red}{\text{that is }q_{n+1}+q_n}&\color{red}{=2(1-x)(q_n+a_n)}\\ \ \\ \text{but } \binom{2n+1}{2i}&=\binom{2n-1}{2i}+2\binom{2n-1}{2i-1}+\binom{2n-1}{2i-2}\\ \text{then } a_n&=\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n-1}{2i}\left(1-x\right)^{n-i}x^{i}} + \sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n-1}{2i-2}\left(1-x\right)^{n-i}x^{i}}\\ &+2 \sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n-1}{2i-1}\left(1-x\right)^{n-i}x^{i}}\\ &=(1-x)\sum_{i=0}^{n-1}{\left( -1\right)^{i}\binom{2n-1}{2i}\left(1-x\right)^{n-1-i}x^{i}} - x\sum_{i=0}^{n-1}{\left( -1\right)^{i}\binom{2n-1}{2i}\left(1-x\right)^{n-i-1}x^{i}}\\ &+2 \sum_{i=1}^{n}{\left( -1\right)^{i}\binom{2n-1}{2i-1}\left(1-x\right)^{n-i}x^{i}}\\ &=(1-2x)a_{n-1}-2x \sum_{i=0}^{n-1}{\left( -1\right)^{i}\binom{2n-1}{2i+1}\left(1-x\right)^{n-1-i}x^{i}}\\ a_n&=(1-2x)a_{n-1}-2x q_{n-1}\\ \ \\ \color{red}{\text{that is }a_{n+1}-a_{n}}&\color{red}{=-2x(a_{n}+ q_{n})}\\ \ \\ \end{align*}

Then by substracting the two red lines \begin{align*} q_{n+1}-a_{n+1}&=q_n+a_n\\ q_{n+1}+a_{n+1}&=q_{n+2}-a_{n+2}\\ 2q_{n+1}&=q_n+q_{n+2}+a_n-a_{n+2}\\ \end{align*} but also \begin{align*} a_{n+2}-a_{n}&=a_{n+2}-a_{n+1}+a_{n+1}-a_{n} \\ &=-2x(a_{n+1}+q_{n+1})-2x(a_{n}+q_{n})\\ &=-2x(a_{n+1}+q_{n+1})-2x(q_{n+1}-a_{n+1})\\ &=-4xq_{n+1}\\ \end{align*} Then \begin{align*} 2q_{n+1}&=q_n+q_{n+2}+a_n-a_{n+2}\\ &=q_n+q_{n+2}+4xq_{n+1}\\ \end{align*} which is the desired result.

Answer 2

Let $$Q_n=\frac{\left(\sqrt{1-x}+{\bf I }\sqrt{x}\right)^{2n+1}}{\sqrt{x}}$$ where ${\bf I}^2 =-1$.

It can be seen with the binomial theorem that $$q_n=\sum_{i=0}^{n}{\left( -1\right)^{i}\binom{2n+1}{2i+1}\left(1-x\right)^{n-i}x^{i}} $$ is the imaginary part of $Q_n$.

We then clearly have \begin{align} Q_{n+1}&=Q_n \left(\sqrt{1-x}+{\bf I }\sqrt{x}\right)^{2}\\ Q_{n-1}&=Q_n \frac{1}{\left(\sqrt{1-x}+{\bf I }\sqrt{x}\right)^{2}} \end{align} This gives readily \begin{align} Q_{n+1}+Q_{n-1}&=Q_n \cdot 2\cdot \left(\sqrt{1-x}^2-\sqrt{x}^{2}\right)\\ &=2(1-2x)Q_n \end{align} And so $q_n$ obey the same order 2 linear recurrence as $p_n$. Since obviously $r_n=p_{n+1}+p_n$ also obey the same order 2 linear recurrence as $p_n$, in order to prove that $q_n= p_{n+1}+p_{n}$, it suffices to check that \begin{align} q_0&=1=p_0+p_1\\q_1&=3-4x= r_1 \\ \text{ since }r_1&=p_2+p_1=2(1-2x)+1=3-4x. \end{align}