The teacher's solution is somewhat problematic in itself as it (ab)uses $a_j$ for two purposes: Once for the "generic" name of the summand in the first line $S_{j+1}=S_j+a_{j+1}$ and then as the numbers from which the summands are computed via $3a_k-2k+3$. Of course in general $a_{j+1}\ne3a_{j+1}-2(j+1)+3$!
I guess the most promising way to prove equations about such summations is as follows:
Consider the left hand side and the right hand side as functions of $n$, say $f(n)=\sum_{k=1}^n(3a_k-2k+3)$ and $g(n)=3\sum_{k=1}^na_k-n^2+2n$. Then show that $f(1)=g(1)$ (you did that). Next concentrate on one side and compute $f(n)-f(n-1)$ for $n>1$, making use of the recursive definition:
$$ \begin{align}f(n)-f(n-1)&=\sum_{k=1}^{n}(3a_k-2k+3)-\sum_{k=1}^{n-1}(3a_k-2k+3)\\&= \left(\sum_{k=1}^{n}(3a_k-2k+3)+(3a_n-2n+3)\right)-\sum_{k=1}^{n-1}(3a_k-2k+3)\\&=3a_n-2n+3.\end{align}$$
Do the same with the right hand side:
$$\begin{align}g(n)-g(n-1)&=\left(3\sum_{k=1}^na_k-n^2+2n\right)-\left(3\sum_{k=1}^{n-1}a_k-(n-1)^2+2(n-1)\right) \\
&=\left(3\sum_{k=1}^{n-1}a_k+3a_n-n^2+2n\right)-\left(3\sum_{k=1}^{n-1}a_k-(n-1)^2+2(n-1)\right)
\end{align}$$
and simplify until you notice that this is just $f(n)-f(n-1)$.
In the string $010100$, $x_1=0$, $x_2=1$, $x_3=1$, $x_4=1$, $x_5=1$, and $x_6=2$: the leading block of $1$’s is empty. The point is that you must have exactly two instances of $01$, so overall the string has to look like
$$\ldots01\ldots01\ldots\;,\tag{1}$$
where the dots must fill in for strings that do not contain $01$. Such strings must be empty, all $0$’s, all $1$’s, or of the form $11\ldots 100\ldots 0$, i.e., a string of $1$’s followed by a string of $0$’s. We can cover all of these possibilities by saying that we’re talking about strings of the form $1^k0^\ell$, meaning $k$ $1$’s followed by $\ell$ $0$’s, where $k$ and $\ell$ are non-negative integers. In particular, they can be $0$. Thus, we can fill out $(1)$ to read
$$1^{k_1}0^{\ell_1}011^{k_2}0^{\ell_2}011^{k_3}0^{\ell_3}\;;$$
this is a string of $k_1$ $1$’s followed by a string of $\ell_1+1$ $0$’s, a string of $k_2+1$ $1$’s, a string of $\ell_2+1$ $0$’s, a string of $k_3+1$ $1$’s, and a string of $\ell_3$ $0$’s. In terms of your notation, $x_1=k_1$, $x_2=\ell_1+1$, $x_3=k_2+1$, $x_4=\ell_2+1$, $x_5=k_3+1$, and $x_6=\ell+3$. As you can see, we can have any non-negative integer values of $x_1,\ldots,x_6$ such that $x_2,x_3,x_4$, and $x_5$ are strictly positive.
Your problem then reduces to counting the solutions in non-negative integers of
$$x_1+x_2+x_3+x_4+x_5+x_6=n\;,$$
subject to the restriction that $x_2,x_3,x_4,x_5\ge 1$. This is a fairly standard stars and bars problem.
Best Answer
This definition of concatenation is really just a more formal way of saying that in order to concatenate a string $w_1$ with a string $w_2$, we first append to $w_1$ the first character of $w_2$, then append to the result the second character of $w_2$, and continue in that fashion until we’ve exhausted $w_2$. For instance, it says that
$$\begin{align*} abc\cdot def&=(abc\cdot de)f\\ &=\big((abc\cdot d)e\big)f\\ &=\big((abcd\cdot\lambda)e\big)f\\ &=\big((abcd)e\big)f\\ &=(abcde)f\\ &=abcdef\;. \end{align*}$$
Note that it’s assumed that we know what it means to append a character to the end of a string; that’s what I did in the last two steps of the calculation.
I’ll prove by induction on the length of $w_2$ that the recursive definition really does tell you how to concatenate a string $w_1\in\Sigma^*$ with any string $w_2\in\Sigma^*$.
The basis step tells you how to concatenate a string $w_1$ with the string of length $0$, i.e., with the empty string: you just get $w_1$ back. Now suppose that you know how to concatenate $w_1$ with any string of length $n$; I claim that the induction step of the definition tells you how to concatenate $w_1$ with any string of length $n+1$. To see this, let $u$ be any string of length $n+1$. Then we can decompose $u$ into a string $w_2$ of length $n$ and a single character $x\in\Sigma$, so that $u=w_2x$. Then $$w_1\cdot w_2=w_1\cdot(w_2x)\;,$$ and the inductive step says that we can rewrite this as $$w_1\cdot w_2=w_1\cdot(w_2x)=(w_1\cdot w_2)x\;.$$ Since by hypothesis we already know how to concatenate $w_1$ with all strings of length $n$, we know how to form $w_1\cdot w_2$. It’s assumed from the beginning that we know what it means to append a single character to a string, so we also know what $(w_1\cdot w_2)x$ is, and therefore we know what $w_1\cdot u$ is. Finally, $u$ was an arbitrary string of length $n+1$, so we see that we now know how to concatenate $w_1$ with any string in $\Sigma^*$ of length $n+1$.
By induction, then, for each $n\in\Bbb N$ and each string $w_2\in\Sigma^*$ of length $n$ we know how to form $w_1\cdot w_2$. Finally, by definition every string in $\Sigma^*$ has length $n$ for some $n\in\Bbb N$, so we know how to form $w_1\cdot w_2$ for each $w_1\in\Sigma^*$.