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?
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.