An innovative recurrence

Dan Sitaru and Leo Giugiuc have posted the following problem and its solution at the CutTheKnotMath facebook page:

Assume $a_1,a_2,a_3,a_4\in\mathbb{N}$ and $a_{a_{n}}=n+4.$

Find $a_{2012}+a_{2013}+a_{2014}+a_{2015}.$


Let's use functional notations: $f(n)=a_{n}$ where $f:\;\mathbb{N}\rightarrow\mathbb{N}.$ Then $f(f(n)=n+4.$ The trick is to express $f(f(f(n)))$ in two ways: one is to replace $n$ with $f(n),$ the other is to apply $f$ to both sides of the identity:

$f(f(f(n)))=f(n)+4,\\ f(f(f(n)))=f(n+4).$

From this


Repeating the steps, $f(n+4)=f(n)+4=f(n-4)+2\cdot 4=f(n-8)+3\cdot 4,$ etc., $f(n)=f(n-4k)+4k,$ $k$ a positive integer.

In particular,

$\begin{align} f(2012)&=f(0)+2012,\\ f(2013)&=f(1)+2012,\\ f(2014)&=f(2)+2012,\\ f(2015)&=f(3)+2012. \end{align}$

In the original terms,

$a_{2012}+a_{2013}+a_{2014}+a_{2015}=a_{0}+a_{1}+a_{2}+a_{3}+4\cdot 2012.$

In general,

$a_{n}= \begin{cases} a_{0}+n, &n=4k,\\ a_{1}+n-1, &n=4k+1,\\ a_{2}+n-2, &n=4k+2,\\ a_{3}+n-3, &n=4k+3.\\ \end{cases}$

This could be expressed with a single formula: $\displaystyle a_{n}=a_{n\,\text{mod}\,4}+4\cdot \left\lfloor\frac{n}{4}\right\rfloor.$

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny