The polynomials $k_n(x_1, \ldots, x_n)$, where $n$ is a non-negative integer, satisfy the following conditions \[k_0=1\] \[k_1(x_1)=x_1\] \[k_n(x_1, \ldots, x_n) = x_nk_{n-1}(x_1, \ldots , x_{n-1}) + (x_n^2+x_{n-1}^2)k_{n-2}(x_1,\ldots,x_{n-2})\] Prove that for each non-negative $n$ we have $k_n(x_1,\ldots,x_n)=k_n(x_n,\ldots,x_1)$.
Problem
Source: Iran 3rd round 2014 - final exam problem 8
Tags: algebra, polynomial, algebra unsolved
16.09.2014 11:13
This is a nice problem, probably inspired by ISL 2013 A1. (You have a few errors in the formulation, however.) First of all we note that polynomial $K_m$ has only monomials with degree $m$, that each monomial appears with coefficient $1$, and that $K_m$ has at most degree $2$ in each of its variables. (This is trivial induction.) Now let's look at how one can get a term in the last polynomial $K_n$. Suppose we have a ladder with $n$ steps. We allow to go up $1$ step or $2$ steps at a time. If we go from step $i-1$ to step $i$, we get an $x_i$, and if we go from step $i-1$ to step $i+1$, then we may choose between $x_i^2$ or $x_{i+1}^2$. And at the end of the climb, we must end up at step $n$. If we multiply all the expressions we got while climbing the ladder up to step $n$, we will get a monomial in $K_n(x_1,x_2,\dots,x_n)$, and conversely, every monomial in $K_n$ can be reached by climbing the ladder in the right way: this follows from the recursion formula. But now we have to climb down the ladder! We begin at an imaginary step $n+1$ - from then on, we can go from step $i+1$ to step $i$ and get an $x_i$, or go from step $i+1$ to step $i-1$ and choose between an $x_i^2$ or an $x_{i-1}^2$. The climb down ends at step $1$. It's clear that climbing down the ladder and multiplying the resulting monomials, we will get a term in $K_n(x_n,x_{n-1},\dots,x_1)$, and the same conversely. We wish to prove that every term in $K_n(x_1,x_2,\dots,x_n)$ appears in $K_n(x_n,x_{n-1},\dots,x_1)$. This is easy with the ladder. In order to get a certain term in $K_n(x_1,x_2,\dots,x_n)$, we must climb on the steps in a certain way; after that, we may climb down the steps such that we can reach this same term in $K_n(x_n,x_{n-1},\dots,x_1)$. Suppose that in the upward climb, the steps we went up $1$ to reach are $a_1,a_2,\dots,a_s$, and the steps we went up $2$ to reach are $b_1,b_2,\dots,b_t$. Then in the downward climb, let's go on the steps $a_1,a_2,\dots,a_s$ and $b_1-1,b_2-1,\dots,b_t-1$. That way, when we step to some $a_i$, we go down $1$, as either we go from $n+1$ to $n$, or from an $a_i$ to another $a_i$, or we go from some $b_i-1$, which was of distance $2$ from the $a_i$ in the upward climb. It's also easy to see that we step $2$ to reach each $b_i-1$. Hence in the downwards climb, we get the exact same $x_{a_i}$'s, and we can again choose between $x_{b_i-1}^2$ and $x_{b_i}^2$. This completes the proof. (Sorry for the sketchiness, but most of the reasoning it pretty straightforward.)