Peter wrote: Let $p \ge 3$ be a prime number. The sequence $\{a_{n}\}_{n \ge 0}$ is defined by $a_{n}=n$ for all $0 \le n \le p-1$, and $a_{n}=a_{n-1}+a_{n-p}$ for all $n \ge p$. Compute $a_{p^3} \; \pmod{p}$. I'm wondering... what makes this problem appear here and not in the L(inear Recurrences) section of PEN? Besides: Is it really a Canada 1986 problem? I can't find it at http://www.math.ca/Competitions/CMO/examt/english86.html or on Kalva. Now, for the solution: I claim that $a_{p^3}\equiv -1\text{ mod }p$. The proof relies on computations with operators acting on sequences. It requires some basics of linear algebra (vector spaces, linear operators and endomorphism rings) that should be known to IMO participants. I will first introduce some notations: A bisequence in a set $K$ will mean a mapping from the set $\mathbb{Z}$ to the set $K$. For any set $K$, we denote by $K^{\mathbb{Z}}$ the set of all bisequences in $K$. Roughly speaking, a bisequence is like a sequence, but its terms are labeled by integers and not by natural numbers. We define a mapping $S:K^{\mathbb{Z}}\to K^{\mathbb{Z}}$ such that, if $u\in K^{\mathbb{Z}}$ is a mapping from the set $\mathbb{Z}$ to the set $K$, then $Su$ is the mapping from the set $\mathbb{Z}$ to the set $K$ defined by $\left(Su\right)\left(x\right)=u\left(x-1\right)$ for every $x\in\mathbb{Z}$. Note that we write $Su$ for $S\left(u\right)$. Roughly speaking, the mapping $S$ shifts every bisequence one term forward. This mapping $S$ is actually called the shift operator. By induction, it can be seen that $\left(S^k u\right)\left(x\right)=u\left(x-k\right)$ for every $k\in\mathbb{Z}$ and every $x\in\mathbb{Z}$. If $K$ is a field, then $K^{\mathbb{Z}}$ can be naturally considered as an (infinite-dimensional) vector space over $K$ as follows: - the zero vector is the "zero bisequence" $0\in K^{\mathbb{Z}}$ defined by $0\left(x\right)=0$ for every $x\in\mathbb{Z}$; - for any two elements $a$ and $b$ of $K^{\mathbb{Z}}$, we define the element $a+b$ of $K^{\mathbb{Z}}$ by setting $\left(a+b\right)\left(x\right)=a\left(x\right)+b\left(x\right)$ for every $x\in\mathbb{Z}$; - for any element $a$ of $K^{\mathbb{Z}}$ and any element $\lambda$ of $K$, we define the element $\lambda a$ of $K^{\mathbb{Z}}$ by setting $\left(\lambda a\right)\left(x\right)=\lambda\cdot a\left(x\right)$ for every $x\in\mathbb{Z}$. It is easily seen that (if $K$ is a field) the transformation $S$ is linear, i. e. it is an endomorphism of this vector space $K^{\mathbb{Z}}$. Note that all endomorphisms of the vector space $K^{\mathbb{Z}}$ form a skew ring; its addition is pointwise addition, its multiplication is composition of endomorphisms; its additive unit is the zero endomorphism (this is the endomorphism sending everything to the zero vector); its multiplicative unit is the identity endomorphism. Now we show a basic fact from algebra, but first a matter of notation: I call a skew ring what most other people just call "ring with $1$" (i. e. a set with an Abelian additive group structure, an associative multiplication with a unit, and distributivity). I, personally, use the word "ring" for commutative skew rings. Two elements $a$ and $b$ of a skew ring are said to commute if $ab=ba$. Lemma 1. Let $p$ be a prime number, and let $R$ be a skew ring such that $p=0$ in $R$ (hereby, $p$ means $\underbrace{1+1+...+1}_{p\text{ ones}}$, and $0$ and $1$ mean the additive and multiplicative units of $R$). If $a$ and $b$ are two elements of $R$ which commute, then $\left(a+b\right)^p=a^p+b^p$. Proof of Lemma 1. Since the elements $a$ and $b$ commute, we can apply the binomial theorem to them, and we obtain $\left(a+b\right)^p=\sum_{k=0}^p\binom{p}{k}a^kb^{p-k}=a^p+\sum_{k=1}^{p-1}\binom{p}{k}a^kb^{p-k}+b^p$. Now, it is known from number theory that $\binom{p}{k}$ is divisible by $p$ for each $k\in\left\{1,2,...,p-1\right\}$ (since $p$ is prime), so that in $R$ we have $\binom{p}{k}=0$ (because $p=0$). Hence, we obtain $\left(a+b\right)^p=a^p+\sum_{k=1}^{p-1}\binom{p}{k}a^kb^{p-k}+b^p=a^p+\sum_{k=1}^{p-1}0a^kb^{p-k}+b^p=a^p+b^p$, and Lemma 1 is proven. Now we can show: Lemma 2. Let $p$ be a prime number with $p\geq 3$, and let $R$ be a skew ring such that $p=0$ in $R$. Let $x$ be an element of $R$. Then, there exists an element $t\in R$ such that $x^{p^2-1}-1=t\left(x^p+x-1\right)$. Proof of Lemma 2. First, since $p=0$ in $R$, we can apply Lemma 1 to any two commuting elements of $R$. Besides, $p$ is odd (since $p$ is a prime and is $\geq 3$), so that $\left(-x\right)^p=-x^p$. Now, since the values of any two polynomials of $x$ with integer coefficients commute with each other, we can compute: $xx^{p^{2}-1}=x^{p^{2}}=\left( x^{p}\right) ^{p}=\left( \left( x^{p}+x-1\right) +\left( 1+\left( -x\right) \right) \right) ^{p}$ $=\left( x^{p}+x-1\right) ^{p}+\left( 1+\left( -x\right) \right) ^{p}$ (by Lemma 1, applied to the commuting elements $x^{p}+x-1$ and $1+\left(-x\right)$ of $R$) $=\left( x^{p}+x-1\right) ^{p}+\left( 1^{p}+\left( -x\right) ^{p}\right) $ (since $\left( 1+\left( -x\right) \right) ^{p} = 1^{p}+\left( -x\right) ^{p}$ by Lemma 1, applied to the commuting elements $1$ and $-x$ of $R$) $=\left( x^{p}+x-1\right) ^{p}+\left( 1+\left( -x\right) ^{p}\right) =\left( x^{p}+x-1\right) ^{p}+\left( 1-x^{p}\right) $ (since $\left( -x\right) ^{p}=-x^{p}$) $=\left( x^{p}+x-1\right) ^{p}-\left( x^{p}+x-1\right) +x$ $=\left( x^{p}+x-1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) +x$, so that $x\left( x^{p^{2}-1}-1\right) =xx^{p^{2}-1}-x$ $=\left( \left( x^{p}+x-1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) +x\right) -x$ $=\left( x^{p}+x-1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) $. Consequently, $x^{p^{2}-1}-1=\left( x^{p}+x\right) \left( x^{p^{2}-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) $ $=\left( x^{p-1}+1\right) x\left( x^{p^{2}-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) $ $=\left( x^{p-1}+1\right) \left( x^{p}+x-1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) $ $=\left( x^{p}+x-1\right) \left( \left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p^{2}-1}-1\right) \right) $ $=\left( \left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p^{2}-1}-1\right) \right) \left( x^{p}+x-1\right) $, and setting $t=\left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right)^{p-1}-1\right) - \left( x^{p^{2}-1}-1\right) $, we get $x^{p^{2}-1}-1=t\left( x^{p}+x-1\right) $, so that Lemma 2 is proven. Now, to the solution of the problem: We define a bisequence $u\in\mathbb{Z}^{\mathbb{Z}}$ recurrently by setting $u\left(n\right)=n$ for all integers $n$ such that $0\leq n\leq p-1$ and the recursion $u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$ for all $n\in\mathbb{Z}$. Note that this recursion has to be applied "forwards" (i. e. in the form $u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$) in order to compute the terms $u\left(p\right)$, $u\left(p+1\right)$, $u\left(p+2\right)$, ..., and applied "backwards" (i. e. in the form $u\left(n-p\right)=u\left(n\right)-u\left(n-1\right)$) in order to compute the terms $u\left(-1\right)$, $u\left(-2\right)$, $u\left(-3\right)$, .... The sequences $\left(u\left(0\right),u\left(1\right),u\left(2\right),...\right)$ and $\left(a_0,a_1,a_2,...\right)$ are equal, because they have the same $p$ starting values ($a_n=n$ and $u\left(n\right)=n$ for all integers $n$ such that $0\leq n\leq p-1$) and satisfy the same $p+1$-term recursion ($a_{n}=a_{n-1}+a_{n-p}$ and $u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$). In other words, $u\left(n\right)=a_n$ for every integer $n\geq 0$. Next, we define a bisequence $\overline{u}\in\left(\mathbb{F}_p\right)^{\mathbb{Z}}$ as follows: For every integer $n$, let $\overline{u}\left(n\right)$ be the residue class of $u\left(n\right)$ modulo $p$. Then, since $u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$ for every $n\in\mathbb{Z}$, we have $\overline{u}\left(n\right)=\overline{u}\left(n-1\right)+\overline{u}\left(n-p\right)$ for every $n\in\mathbb{Z}$. Since $\overline{u}\left(n-1\right)=\left(S\overline{u}\right)\left(n\right)$ and $\overline{u}\left(n-p\right)=\left(S^p\overline{u}\right)\left(n\right)$, this becomes $\overline{u}\left(n\right)=\left(S\overline{u}\right)\left(n\right)+\left(S^p\overline{u}\right)\left(n\right)$ for every $n\in\mathbb{Z}$. Hence, $\overline{u}=S\overline{u}+S^p\overline{u}$, so that $\left(S^p+S-1\right)\overline{u}=0$ (hereby, $1$ stands for the identity endomorphism of $\left(\mathbb{F}_p\right)^{\mathbb{Z}}$; in fact, we can call it $1$ because it is the multiplicative unit of the skew ring of endomorphisms of $\left(\mathbb{F}_p\right)^{\mathbb{Z}}$). The skew ring of endomorphisms of the vector space $\left(\mathbb{F}_p\right)^{\mathbb{Z}}$ satisfies $p=0$ (since $p=0$ holds in $\mathbb{F}_p$). Thus, applying Lemma 2 to the element $x=S$ of this skew ring, we see that there exists an element $T$ of this skew ring such that $S^{p^2-1}-1=T\left(S^p+S-1\right)$. Hence, $S^{p^3-p}-1=\left(S^{p^2-1}\right)^p-1=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot \left(S^{p^2-1}-1\right)$ $=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\left(S^p+S-1\right)$. Thus, $\left(S^{p^3-p}-1\right)\overline{u}=\left(\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\left(S^p+S-1\right)\right)\overline{u}$ $=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\cdot\underbrace{\left(S^p+S-1\right)\overline{u}}_{=0}=0$, so that $S^{p^3-p}\overline{u}=1\overline{u}$. This yields that $\left(S^{p^3-p}\overline{u}\right)\left(n\right)=\left(1\overline{u}\right)\left(n\right)$ for every $n\in\mathbb{Z}$. In other words, $\overline{u}\left(n-\left(p^3-p\right)\right)=\overline{u}\left(n\right)$ for every $n\in\mathbb{Z}$. Applying this to $n=p^3$, we get $\overline{u}\left(p^3-\left(p^3-p\right)\right)=\overline{u}\left(p^3\right)$. In other words, $\overline{u}\left(p\right)=\overline{u}\left(p^3\right)$. Since $\overline{u}\left(n\right)$ was defined as the residue class of $u\left(n\right)$ modulo $p$, this equation yields that $u\left(p\right)\equiv u\left(p^3\right)\text{ mod }p$. Since $u\left(n\right)=a_n$ for all integers $n\geq 0$, this rewrites as $a_p\equiv a_{p^3}\text{ mod }p$. Now, applying the recursion $a_{n}=a_{n-1}+a_{n-p}$ to $n=p$, we get $a_p=a_{p-1}+a_{p-p}=a_{p-1}+a_0=\left(p-1\right)+0=p-1$. Thus, $a_p\equiv a_{p^3}\text{ mod }p$ yields $p-1\equiv a_{p^3}\text{ mod }p$, so that $a_{p^3}\equiv p-1\equiv -1\text{ mod }p$. This completes the proof. PS. In the above, I showed that $a_{p^3}\equiv -1\text{ mod }p$ for every prime $p\geq 3$. By inspection you can see that this also holds for $p=2$. Darij

This is indeed not from Canada 1986... does anyone know the correct source?