I've come across a nice little combinatorial problem. Firstly we have vector $(1, 1)$. On each iteration for each two consecutive numbers in the vector we add their sum between them: $$(1, 2, 1)$$ $$(1, 3, 2, 3, 1)$$ $$(1, 4, 3, 5, 2, 5, 3, 4, 1)$$ $$(1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1)$$ ad infinitum.
Here's the question. How many times number $n$ will be written in the final vector? I'v computed the answers for $1, \dots, 15$: $$2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8$$
And this values coincide with the values of Euler's totient function. But how to prove that the answer is always $\phi(n)$? And can one simply derive this idea without explicitly writing first values?
Let's first name the vectors $v_1, v_2$ and so on.
First of all we can note that consecutive numbers in the vector are coprime by induction. The base case is trivial. Now assume it holds for $v_{n-1}$ and consider $v_n$. Let $a,b$ are consecutive number in $v_n$. Then because of the way numbers are added to the vectors we have $a,|b-a|$ or $b, |a-b|$ appearing as consecutive numbers in $v_{n-1}$. WLOG let it be the first option. But then $\gcd(a,b) = \gcd(a,|b-a|) =1$. Hence the proof.
Now let's notice that a number $n$ can appear in the vector if $a,b$ appear as consecutive integer in a vector and $a+b = n$. But from above we have that neither of $a,b$ can share a common factor of $n$. Now using induction on $n$ we'll prove that such a combination of consecutive integers $(a,b)$ can appear only in a unique vector. The base case for $n=1,2,3$ is true. Now assume that we have consecutive integers $a,b$ appearing in different vectors, namely $v_i$ and $v_j$ such that both sum to $n$. WLOG let $a<b$. Then going back in $v_{i-1}$ and $v_{j-1}$ we have the consecutive integers $a, b-a$ in both vectors. But this contradicts the inductive hypothesis as both pairs sum to $b<n$.
From here we can conclude that an integer $n$ will be at most $\phi(n)$ in the final vector. Now it remains to show that each combination of $a,b$ s.t. $\gcd(a,b) = 1$ appears as consecutive integers at some point.
[UPDATE]
Similar as above we'll prove the last claim by induction on $n$. The base cases $n=1,2,3$ are trivially true. Now assume the claim holds for all numbers less than $n$. Now let $a,b$ be any integers such that $a+b=n$ and $\gcd(a,b)=1$ and WLOG $a<b$. We know that they will appear in $v_i$ if and only if $a,b-a$ appear as consecutive integers in $v_i$. But by the inductive hypothesis we have that $a,b-a$ does appear as consecutive integers in a unique vector. Therfore $a,b$ appear too and in a unique vector. Hence the proof.
SUMMARY: We can count the pairs of the consecutive integers by their left member and summarizing from above we have that if $a<n$ and $\gcd(a,n) = 1$, then eventually the integers $a,n-a$ will appear only once in the vectors. Note that the case $n-a,a$ is counted by using $n-a$. Therefore each integers appears $\phi(n)$ times in the final vector.