Proving that $u_n(t)^2 - u_k(t)^2 = u_{n-k}(t)u_{n+k}(t)$ given a recurrence relation

Question

$$u_0(t)=0, \ u_1(t) = 1, \ u_n(t) = tu_{n-1}(t) - u_{n-2}(t)$$ I need to prove that $u_n(t)^2 - u_k(t)^2 = u_{n-k}(t)u_{n+k}(t), \ k =0,1,\dots,n$.

I tried to prove statement by induction:

Let $u_{k'}(t)^2 - u_k(t)^2 = u_{k'-k}(t)u_{k'+k}(t)$.

Then: $$\begin{split}u_{k' + 1}(t)^2 - u_k(t)^2 &= (tu_{k'}(t) - u_{k'-1}(t))^2 - u_k(t)^2\\ &= u_{k'-1-k}(t)u_{k'-1+k}(t) - 2tu_{k'}(t)u_{k'-1}(t) + t^2u_{k'-k}(t)u_{k'+k}(t) + t^2u_k(t)^2\end{split}$$

This result seems useless to me.

I tried to use this formula: $u_n(t) = t^{n-1} - {n-2 \choose 1}t^{n-3} + {n-3 \choose 2}t^{n-5} + \cdots$ (which is easily proved by induction)

But it's complicated to work with product of two sums.

Answer 1

I proved it using difference equations (not to be confused with differential equations), I will not provide a derivation for the general solution of the difference equation here though since the proof is already too long, but if you like video content, Michael Penn has an excellent video deriving the general solution to such difference equation.

For notation simplicity, I'll let $a_n = u_n(t)$. From the recurrence relation you described we can see that

$$\begin{align} a_n &= t a_{n-1} - a_{n-2} \\ a_{n+2} &= ta_{n+1} - a_n \\ a_0 &= 0 \\ a_1 &= 1 \\ \end{align}$$

This relation describes a homogeneous linear difference equation with constant coefficients ($t$ is considered constant since it's not a function of $n$), the characteristic equation of which is

$$ r^2 - t r + 1 = 0 \\ r_{1,2} = \frac{t \pm \sqrt{t^2 - 4}}{2} $$

The roots, $r_1$ and $r_2$, are equal when $\sqrt{t^2 - 4} = 0 \iff t = \pm 2 \iff |t| = 2$, and we have distinct roots otherwise, so we have two cases to consider here:

1. The roots are the same, $|t| = 2$.
2. The roots $r_1$ and $r_2$ are distinct, $|t| \ne 2$.

Let's start with case 1 since it's more straightforward.

In the case of a single root $r$, the solution to our given difference equation is given by

$$a_n = Ar^n + Bnr^n = (A + Bn)r^n$$

Substituting the value for $a_0$ in the function above we get

$$\begin{align} a_0 = 0 &= (A + B \cdot 0)r^0 \\ A &= 0 \end{align}$$

so our function simplifies to

$$a_n = Bnr^n$$

If $t = 2$, then the characteristic equation will be $r^2 - 2r + 1 = 0$, the left hand side is a perfect square so $(r - 1)^2 = 0$ and we have $r = 1$. Similarly, if $t = -2$, we get $r = -1$. So the only values $r^n$ could take are $1$ (for all $n$ if $r = 1$ and for even $n$ if $r = -1$) and $-1$ (for odd $n$ when $r = -1$).

Now let's prove the statement you gave for case 1.

The left-hand side is $$\begin{align} a_n^2 - a_k^2 &= (Bnr^n)^2 - (Bkr^k)^2 \\ &= B^2 n^2 r^{2n} - B^2 k^2 r^{2k} \\ &= B^2 n^2 - B^2 k^2 \\ &= B^2 (n^2 - k^2) \\ &= B^2 (n + k) (n - k) \end{align}$$ Notice the $r^{2n}$ and $r^{2k}$ are always equal to $1$ regardless of whether $r = 1$ or $r = -1$.

The right-hand side is $$\begin{align} a_{n + k} a_{n - k} &= B(n + k)r^{n + k} \cdot B(n - k)r^{n - k} \\ &= B^2 r^{2n + k - k} (n + k) (n - k) \\ &= B^2 r^{2n} (n + k) (n - k) \\ &= B^2 (n + k) (n - k) = \text{L.H.S} \end{align}$$

Now let's consider case 2 where roots are distinct. In such case, the general solution to $a_n$ is given by

$$a_n = Ar_1^n + Br_2^n$$

Again, substituting in the equation $a_0 = 0$ we get

$$\begin{align} a_0 = 0 &= Ar_1^0 + B r_2^0 \\ 0 &= A + B \\ B &= -A \end{align}$$

so our function simplifies to

$$a_n = A(r_1^n - r_2^n)$$

From the characteristic equation, it's easy to see that the product of our roots $r_1 r_2$ is always $1$, we'll use this fact throughout the proof for case 2.

Now we prove the statement with case 2.

The left-hand side is $$\begin{align} a_n^2 - a_k^2 &= A^2(r_1^n - r_2^n)^2 - A^2(r_1^k - r_2^k)^2 \\ &= A^2 \big( r_1^{2n} - 2 r_1^n r_2^n + r_2^{2n} - r_1^{2k} + 2 r_1^k r_2^k - r_2^{2k} \big) \\ &= A^2 \big( r_1^{2n} + r_2^{2n} - r_1^{2k} - r_2^{2k} - 2 (r_1 r_2)^n + 2 (r_1 r_2)^k \big) \\ &= A^2 \big( r_1^{2n} + r_2^{2n} - r_1^{2k} - r_2^{2k} - 2 \cdot 1^n + 2 \cdot 1^k \big) \\ &= A^2 \big( r_1^{2n} + r_2^{2n} - r_1^{2k} - r_2^{2k}\big) \end{align}$$

The right-hand side is $$\begin{align} a_{n + k} a_{n - k} &= A(r_1^{n + k} - r_2^{n + k}) \cdot A(r_1^{n - k} - r_2^{n - k}) \\ &= A^2 \big(r_1^{2n} + r_2^{2n} - r_1^{n + k}r_2^{n - k} - r_2^{n + k} r_1^{n - k} \big) \\ &= A^2 \big(r_1^{2n} + r_2^{2n} - r_1^{n - k} r_2^{n - k} (r_1^{2k} + r_2^{2k}) \big) \\ &= A^2 \big(r_1^{2n} + r_2^{2n} - (r_1 r_2)^{n - k} (r_1^{2k} + r_2^{2k}) \big) \\ &= A^2 \big(r_1^{2n} + r_2^{2n} - (r_1^{2k} + r_2^{2k}) \big) \\ &= A^2 \big(r_1^{2n} + r_2^{2n} - r_1^{2k} - r_2^{2k} \big) = \text{L.H.S} \quad \blacksquare \\ \end{align}$$

Proving case 2 and thus completing the full proof.

Answer 2

This question is about the sequence of polynomials given by

$$ u_0(t)=0, \quad u_1(t) = 1, \quad u_n(t) = t\,u_{n-1}(t) - u_{n-2}(t). \tag1 $$

There are several methods available. One method is to recognize that

$$ u_n(t) = U_{n-1}(t/2) \tag2 $$

where $\,U_n(x)\,$ is the Chebyshev polynomial of the second kind. A known property of them is that

$$ U_{n-1}(\cos\theta) = \sin(n\theta)/\sin(\theta). \tag3 $$

Thus, let $\, t = 2\cos(\theta)\,$ to get

$$ u_n(t) = \sin(n\theta)/\sin(\theta). \tag4 $$

The result to prove is

$$ u_n(t)^2 - u_k(t)^2 = u_{n-k}(t)u_{n+k}(t). \tag5 $$

Use equation $(4)$ and elementary algebra to get the equivalent

$$ \sin(n\theta)^2 - \sin(k\theta)^2 = \sin((n-k)\theta)\sin((n+k)\theta). \tag6 $$

This trigonometric identity can be proven in several ways. One of the simplest is to use the representation of the sine using the exponential function and elementary algebra to get

$$ \Big(x-\frac1{x}\Big)^2-\Big(y-\frac1{y}\Big)^2 = \Big(\frac{x}{y}-\frac{y}{x}\Big) \Big(xy-\frac1{xy}\Big). \tag7 $$

---

An alternative method using recursion is as follows. First, since $\,t\,$ is fixed, drop it from the notation. That is, $u_n := u_n(t).$

Recognize that $\,u_n\,$ is the Lucas sequence of the first kind. That is, $\, u_n = U_n(t,1).\,$

The next step is to prove for a fixed $\,k\,$ the addition theorem

$$ u_{n+k} = u_n u_{k+1} - u_{n-1} u_k. \tag8 $$

A standard technique is to verify that both sides of the equality have the same two initial values and the same recursion as $\,u_n.\,$ Then the equality is true for all $\,n\,$ by induction. Same thing for

$$ u_{n-k} = u_{n-1} u_k - u_n u_{k-1}. \tag9 $$

Combine equations $(8)$ and $(9)$ to get

$$ u_{n-k}u_{n+k} = (u_{n-1} u_k - u_n u_{k-1})(u_n u_{k+1} - u_{n-1} u_k) =: T_{n,k}. \tag{10} $$

Next, prove that the sum and product of $\,u_{n-1}\,$ and $\,u_{n+1}\,$ is

$$ u_{n-1}+u_{n+1} = t\,u_n, \quad u_{n-1}u_{n+1} = u_n^2 - 1 \tag{11} $$

by induction using the recursion equation $(1)$ and elementary algebra.

Expand $\,T_{n,k},\,$ the right side of equation $(10)$ to get

$$ T_{n,k} = u_n u_{n-1}u_k( u_{k+1}+u_{k-1}) - u_n^2u_{k-1}u_{k+1} - u_k^2u_{n-1}u_{n+1}. \tag{12} $$

Finally, use the results in equation $(11)$ to get

$$ T_{n,k}=(u_n^2-1)u_k^2-u_n^2(u_k^2-1) = u_n^2-u_k^2.\tag{13}$$