<s>[INST] How to solve patterns Let's take an example of the pattern
$T_1 = 1$
$T_2 = 6$ // $T_2 = 1 + 8 - 3 = 6$
$T_3 = 15$ // $T_3 = 6 + 12 - 3 = 15$
$T_4 = 28$ // $T_4 = 15 + 16 - 3 = 28$
If you noticed, the pattern is $T_n = T_{n-1} + 4n - 3$
So, is there a way to solve this without recursion?
 [/INST] We solve:
$$T(n) = T(n-1) + 4n - 3$$
Thus
$$T(n) - T(n-1) = 4n - 3$$
since the difference of $$T(n) - T(n-1)$$ is linear ($4n-3$ is a linear term): the original function $T(n)$ must be quadratic.
Why?
Consider an arbitrary quadratic
$$H(n) = an^2 + bn + c $$
$$H(n) - H(n-1) = an^2 + bn + c - a(n-1)^2 -b(n-1) - c = $$
$$an^2 + bn + c - a(n^2 - 2n + 1) - b(n-1) - c = $$
$$an^2 + bn + c - an^2 + 2an - a - bn + b - c = $$
$$bn + c + 2an - a - bn + b - c = $$
$$c + 2an - a + b - c = $$
$$2an - a + b$$
if $2a = u$ and $b - a = k$ then we get an arbitrary linear function $un + k$. Thus if the difference of two functions is linear the original recurrence function is quadratic.
Coming back to the problem at hand:
$$2an + b - a = 4n - 3$$
$$2a = 4 \rightarrow a = 2$$
$$b - a  = -3 \rightarrow b - 2 = -3 \rightarrow b = -1$$
$$T(n) = 2n^2 - n + c$$
$$T(1) = 2 - 1 + c = 1 + c = 1 \rightarrow c = 0$$
$$T(n) = 2n^2 - n$$
</s>