<s>[INST] Suppose that $na_{n}=(n−3)a_{n−1}+n$ for n>2 with $a_{0}=a_{1}=a_{2}=0$. What is the value of $a_{999} $​? Suppose that $$na_{n}=(n−3)a_{n−1}+n$$ for $n>2$ with $a_{0}=a_{1}=a_{2}=0$. What is the value of $a_{999} $?
This is a question on solving recurrence relations that I just can't wrap my stupid head around. Would appreciate any input on how to solve these kind of problems. Yes, I know I am stupid, but I love math, please, don't block me. Analytic combinatorics is hard
 [/INST] We will prove that for all $n \geq 3$ we have $a_n = \frac{n+1}{4}$, by induction on $n$. Notice that for all $n \geq 3$ we have $a_n = (1 - \frac{3}{n})a_{n-1} + 1$.
For $n = 3$ one can compute $a_3 = (1 - \frac{3}{3})a_2 + 1 = 1 = \frac{3 + 1}{4}$.
Now suppose that the induction hypothesis is true for $n = k > 3$, i.e. $a_k = \frac{k+1}{4}$. For $n = k+1$ we can write:
\begin{align*}
a_{k+1} = (1 - \frac{3}{k+1})a_{k} + 1 = \frac{k-2}{k+1} \times \frac{k+1}{4} + 1 = \frac{k-2}{4} + 1 = \frac{k+2}{4} = \frac{(k+1) + 1}{4}
\end{align*}
That is what we wanted.
Therefore, $a_{999} = \frac{999+1}{4} = 250$.
</s>