Solving without induction show that $a_{n}=2n-1$

If we want to solve this without any guessing and without using induction in any way, the best way to do so is to work with generating functions. This method, given that it really makes no assumptions on the final form, takes considerably more work, but can also solve generalizations of this problem.

In particular, the big trick is to consider the 'function' defined as $$a(x) = a_1+a_2x+a_3x^2+\ldots.$$ We treat this as a formal sum, meaning we ignore any issues of convergence and just treat it algebraically. We then express the recurrence relation as an equation on $a(x)$ and use that to find $a(x)$ and then work backwards to find the coefficients $a_i$. A bit more explaining is necessary for why calculus works, but let's ignore those issues.

So, our equation is $$4S_n=n(a_n+a_{n+1}).$$ First, we can express the left hand side using another generating function: $$S(x)=S_1+S_2x+S_3x^2+\ldots.$$ A well known relation lets us write $S(x)$ in terms of $a(x)$: \begin{align*}S(x)=\frac{a(x)}{1-x}=a(x)\cdot (1+x+x^2+\ldots)=a_1&+a_2x+a_3x^2+\ldots\\&+a_1x + a_2x^2+\ldots \\&\hskip.45in +a_1x^2+\ldots\end{align*} where we use $\frac{1}{1-x}=1+x+x^2+\ldots$ and the last equality shows the distribution of this over $a(x)$, noting that each column is a partial sum.

For the other side, we have $n$, which hints that we should try differentiating something with coefficients of $a_n+a_{n+1}$. In particular, let $$B(x)=(1+x)a(x)= a_1+(a_1+a_2)x + (a_2+a_3)x^2 + \ldots$$ and note its derivative $$B'(x)=(a_1+a_2) + 2(a_2+a_3)x + 3(a_3+a_4) + \ldots.$$ If we see that he coefficients of $x^{n-1}$ in $B'(x)$ are $n(a_n+a_{n+1})$ and the coefficients of $x^{n-1}$ in $S(x)$ are $S_n$, we get that we want $$4S(x)=B'(x)$$ Note that the product rule gives $B'(x)=a(x) + (1+x)a'(x)$. Expanding both sides in terms of $a$ gives $$\frac{4a(x)}{1-x}=a(x) + (1+x)a'(x)$$ which is a differential equation. Then, we can rearrange this equation as $$\frac{(3+x)a(x)}{1-x^2}=a'(x)$$ $$\frac{3+x}{1-x^2}=\frac{a'(x)}{a(x)}$$ The left side may be pulled apart using partial fractions $$\frac{1}{1+x}+\frac{2}{1-x}=\frac{a'(x)}{a(x)}.$$ Integrating both sides in $x$ gives $$\log(1+x) - 2\log(1-x) + C_1 = \log(a(x))$$ Taking exponents of both sides, and letting $C_2=e^{C_1}$ gives $$C_2\cdot \frac{1+x}{(1-x)^2}=a(x)$$ Moreover, noting that the constant term on the left is just $C_2$, we get $C_2=a_1=1$ thus $$\frac{1+x}{(1-x)^2}=a(x)$$ Then, we break this up by partial fractions to yield $$\frac{-1}{1-x}+\frac{2}{(1-x)^2}=a(x).$$ This is convenient. It is well known that we have $\frac{1}{1-x}=1+x+x^2+\ldots$ and $\frac{1}{(1-x)^2}$ can be seen to be $1+2x+3x^2+4x^3+\ldots$ by various methods. Thus, the coefficient of $x^n$ on the left will be $-1 + 2(n+1)=2n+1$. This must equal the coefficient $a_{n+1}$ on the right side so $2n+1=a_{n+1}$ meaning $2n-1=a_n$.


It is worthy of note that, if one applies the proper framework to this, the fact that the algebra checks out is sufficient to prove the correctness of this - that is, we don't need to go back and prove that our system satisfies the original conditions. Moreover, the same framework quickly can solve things like $6S_n=n(a_n+a_{n+1})$, where the answer is harder to guess; in this particular case, we'd get $$a(x)=\frac{(1+x)^2}{(1-x)^3}=\frac{4}{(1-x)^3}- \frac{4}{(1-x)^2} + \frac{1}{1-x}=\sum_{n=0}^{\infty}(2(n+1)(n+2) - 4(n+1) + 1)x^n$$ which gives $a_n=1-2n+2n^2$.