How to calculate the result of this repeating additions quickly We're given an exercise for a programming lesson. It goes like this:
Starts with an array, ranging from $1$ to $n$. At every iteration, add $2$ neighboring numbers together. Stop when the amount of numbers in the array reaches $1$.
Here's a visual representation:
1  2  3  4  5
 \/ \/ \/ \/
 3  5  7  9
  \/ \/ \/
  8  12 16
   \/  \/
   20  28
    \  /
     48

The problem is, doing this step by step took way too much time, especially when we have to deal with $n = 2018201820182018$. So, is there a way to calculate the final number without doing the addition?
EDIT: We're allowed to do a modulus of the answer with $10^9$, and I've found a formula for calculating the final number: $(n+1) * 2^{(n-2)}$, but the latter part still gives a very large result. Are there any other formulas?
 A: This is more like a long comment than an answer.
If you take Lord Shark's advice and set $a_1=1$, $a_2=2$, $a_3=3$, $a_4=4$, and $a_5=5$, and then express every other number in your example in terms of $a_1$, $a_2$, $a_3$, $a_4$, and $a_5$, an interesting and familiar pattern emerges.
We start out pretty simply:
\begin{align}
3&=a_1+a_2 \\
5&=a_2+a_3 \\
7&=a_3+a_4 \\
9&=a_4+a_5
\end{align}
The next step is where we start to see the pattern:
\begin{align}
8&=(a_1+a_2)+(a_2+a_3)=\color{red}1a_1+\color{red}2a_2+\color{red}1a_3 \\
12&=(a_2+a_3)+(a_3+a_4)=\color{red}1a_2+\color{red}2a_3+\color{red}1a_4 \\
16&=(a_3+a_4)+(a_4+a_5)=\color{red}1a_3+\color{red}2a_4+\color{red}1a_5
\end{align}
And it becomes even clearer in the last two steps:
\begin{align}
20&=(a_1+2a_2+a_3)+(a_2+2a_3+a_4)=\color{red}1a_1+\color{red}3a_2+\color{red}3a_3+\color{red}1a_4 \\
28&=(a_2+2a_3+a_4)+(a_3+2a_4+a_5)=\color{red}1a_2+\color{red}3a_3+\color{red}3a_4+\color{red}1a_5
\end{align}
\begin{align}
48=(a_1+3a_2+3a_3+a_4)+(a_2+3a_3+3a_4+a_5)=\color{red}1a_1+\color{red}4a_2+\color{red}6a_3+\color{red}4a_4+\color{red}1a_5
\end{align}
See those coefficients? I think the binomial theorem might come in handy.
