Solve the recurrence relation $a_{n+1} = 10a_n+n+1$, $\forall n\ge0$ with $a_0= 0$ I am trying to solve this recurrence relation. I'm currently in discrete with graph theory and have not taken linear algebra / differential equations so I don't have the largest toolbox for solving these type of problems.
I understand that $p(n)$ can be any particular solution to the relation, and $q(n)$ can be the general solution, therefore $a_n = p(n) + q(n)$
So if I take $p_n = a + bn$
can I just directly plug that into the initial equation getting:
$a(n+1) + b = 10(an + b) + n + 1$ ?
or am I completely missing the mark here?
If there is a youtube video, or some other video that you would recommend I would be extremely grateful. I would really like to understand this better.
 A: We have
$$a_1=1$$
$$a_2=10×1+2$$
$$a_3=10(10×1+2)+2+1=10^2+2×10+3$$
$$a_4=10(10^2+2×10+3)+3+1=10^3+2×10^2+3×10+4$$
$$a_5=10(10^3+2×10^2+3×10+4)+4+1=10^4+2×10^3+3×10^2+4×10+5$$
Finally,  by induction we have:
$$\begin{align}\color {gold}{\boxed {\color{black}{a_0=0, ~a_n=\sum_{k=1}^{n} k10^{n-k}}}}\end{align}$$

It is possible to prove that
$$\begin{align}\color {gold}{\boxed {\color{black}{a_0=0,~ a_n=\sum_{k=1}^{n} k10^{n-k}=\frac{1}{81} (10^{n+1} - 9n-10).}}}\end{align}$$
A: Hint
This problem was here some days ago. I will write the same hint I wrote before.
$$a_{n+1} = 10a_n+n+1$$
$$a_{n} = 10a_{n-1}+(n-1)+1$$
Now, subtract both equations,
$$a_{n+1}-a_n = 10(a_n-a_{n-1})+1$$
Can you finish?
A: Write the equation as $$a_{n+1}-10a_n=n+1\tag1$$
This is an inhomogeneous linear difference equation.  ("Inhomogeneous" because the right-hand side is not $0$).  The corresponding homogeneous equation is $$a_{n+1}-10a_n=0\tag2$$  The theorem you are thinking of is that the general solution to $(1)$ is the general solution to $(2)$ plus any particular solution to $(1)$.
The general solution to $(2)$ is $$a_n=10^nk$$ for some constant $k$.  To find the a particular solution of $(1)$, because the right hand side is a linear polynomial, we guess that there will be a particular solution that is also of this form: $a_n=cn+d.$  Substituting into $(1)$ gives $$
c(n+1)+d = 10(cn+d)+n+1\\
cn+c+d=10cn+10d+n+1\\
c-1-9d=(9c+1)n$$
To eliminate the $n$, we take $c=-\frac19$.  Then $d=-\frac{10}{81}$ giving $$a_n=-\frac{9n+10}{81}$$ as a particular solution to $(1)$.  (You should check this.)
Now the general solution to $(1)$ is $$a_n=10^nk-\frac{9n+10}{81}$$ and we have only to determine $k$ by substituting $a_0=0$. I'll leave that part for you.
A: You can use a simple trick to solve this problem easily: Note that given sequence is "roughly" a GP (apparent from the given recursive step). So let's do a translation to make it a GP exactly. Define $b_n = a_n+kn+l$. Now the recursion becomes
\begin{align}
&b_{n+1}-k(n+1)-l = 10b_n-10kn-10l+n+1\\
\implies&b_{n+1}=10b_n+n(-9k+1)+k+1-9l
\end{align}
Solving for the coefficient of $n$ and constant term to be zero, we get $k=\frac19$ and $l=\frac{10}{81}$. Now apply the general formula for the GP get $b_n$ and hence get $a_n$.
