There's a list of $30$ numbers in which the first number is $1$ and the last is $30$. The other numbers exceed in one the average of their two neighbours (I don't know if that was grammatically correct but basically, assuming that $a_k$ is the $k^{th}$ number on the list, you could calculate using the formula above on the title). What is the biggest number on the list?
I tried to solve this question but couldn't, so luckily I could see the solution. It was:
$ 2a_k=a_{k-1}+a_{k+1}+2$ for $k = \{2,..., 30 \}$ and then $ a_{k+1}= 2a_k - a_{k-1} - 2$. Suppose that $a_2 = x$, then:
$a_3 = 2a_2 - a_1 -2= 2x-3$ since $a_1=1$
$a_4 = 2a_3 - a_2 -2= 2(2x-3) - x- 2= 3x-8$
$a_5 = 2a_4 - a_3 -2= 2(3x-8)-(2x-3) -2=4x-15$
$a_6 = 2a_5 - a_4 -2= 2(4x-15) - (3x-8) -2= 5x-24$
So, here they say that $a_k= (k-1)x-k(k-2)$ and since $a_{30}= 30$ it would be possible to find the value of $x$ and then solve the question. But to do that you would first have prove that $a_k= (k-1)x-k(k-2)$ is true for all posible values of $k$ but unfornately the said that the proof by induction was left out.
I tried to do it but couldn't prove anything. I just know how to use like the most common method in induction so I think that it may be possible to prove with the other ones. Any hint or help will be accepted, thanks in advance.
Ok, let's prove by induction that $a_k = (k-1)x-k(k-2)$, where $x=a_2$:
Since the formula $a_{k+1}=2a_k-a_{k-1}-2$ 'reaches back' to the previous two entries, you need two base cases:
$k=1$. Then $a_1=0x-1(1-2)=0+1=1$ Check!
$k=2$. Then $a_2=(2-1)x-2(2-2)=x$ Check!
And for the step, you need two inductive hypotheses: Assume $a_k=(k-1)x-k(k-2)$, and $a_{k-1}=(k-1-1)x-(k-1)(k-1-2)=(k-2)x-(k-1)(k-3)$
Then:
$a_{k+1}=2a_k-a_{k-1}-2=2(k-1)x-2k(k-2)-(k-2)x+(k-1)(k-3)-2=$
$2kx-2x-kx+2x-2k^2+4k+k^2-4k+3-2=kx-k^2+1=$
$kx-(k+1)(k-1)=((k+1)-1)x-(k+1)((k+1)-2)$
as desired. Check!