$$a_k = \left\{ \begin{array}{lr} 2a_{k-1} - a_{k-2} &: if \space k > 2 \\ 3 & :if\space k =2 \\ 2 & :if \space k =1 \end{array} \right.$$
It's easy to see that the nth term is n+1 based on the pattern but how do I actually show it? Is there a general way to solve these recurrence problems?
The only way I can think of is $a_k - a_{k-1}=a_{k-1}-a_{k-2}$ implies arithmetic progression, so based on that n+1
The more general approach would be to write a characteristic equation
$$x^k=2x^{k-1}-x^{k-2}$$
and simplify this to $$x^2=2x-1$$ which has the double solution $x=1$.
It there had been two distinct solutions $\beta$ and $\gamma$ then a general solution to the recurrence would be $a_k= A\beta^k+B\gamma^k$ and you would find $A$ and $B$ by looking at the initial terms. But if there a double solution $\beta$ to the characteristic equation then a general solution to the recurrence would be $a_k= A\beta^k+Bk\beta^k$. With longer linear recurrences, there may be more roots, and a similar approach works.
Here we are in the latter situation and $\beta=1$, so the solution is of the form $a_k=A+Bk$, and the initial terms $a_1=2, a_2=3$ tell us $A=1, B=1$ and thus $$a_k=1+k.$$
