Induction troubles proving a formula. I'm having a tough time proving the following formula. Suppose $a,b\in R$ a ring. Define $a^{(0)}=a$, $a^{(1)}=[a,b]\equiv ab-ba$, and then $a^{(k)}=[a^{(k-1)},b]$. Then
$$
\sum_{i=0}^k b^iab^{k-i}=\sum_{j=0}^k\binom{k+1}{j+1}b^{k-j}a^{(j)}.
$$
I wanted to do this with induction on $k$, but the presence of $k$ in each term of the sum is making it difficult to get the right form of things. I had something like
$$
\begin{align*}
\sum_{i=0}^{k+1}\binom{k+2}{j+1}b^{k+1-j}a^{(j)} &=
\sum_{j=0}^k \binom{k+2}{j+1}b^{k+1-j}a^{(j)}+a^{(k+1)}\\
&= \sum_{j=0}^k\left[\binom{k+1}{j}+\binom{k+1}{j+1}\right]b^{k+1-j}a^{(j)}+a^{(k+1)}\\
&=b\sum_{j=0}^k\binom{k+1}{j}b^{k-j}a^{(j)}+b\sum_{j=0}^k\binom{k+1}{j+1}b^{k-j}a^{(j)}+a^{(k+1)}\\
&=b\sum_{j=0}^k\binom{k+1}{j}b^{k-j}a^{(j)}+b\sum_{i=0}^k b^iab^{k-i}+a^{(k+1)}
\end{align*}
$$
but this is still far from what I want. I tried doing induction in the other direction, but had similar problems. I don't see how the recursive definition of $a^{(k)}$ comes into play. How can the formula be properly derived? Thanks.

Denote the LHS terms as
$$S_k=\sum_{i=0}^k b^i a b^{k-i}.$$
Notice this satisfies the recurrence
$$S_{k+1}=\sum_{i=0}^{k+1} b^i a b^{k+1-i}=\left(\sum_{i=0}^k b^iab^{k+1-i}\right)+b^{k+1}ab^{k+1-(k+1)}=S_kb+b^{k+1}a.$$
If you establish that $S_k$ and the RHS are equal as a base case, we need only prove that the RHS also satisfies this recurrence so they are the same sequence (as the recurrence solution is unique).
It helps to first note that $a^{(k)}b=ba^{(k)}+a^{(k+1)}$ using the inductive definition.
Now take the RHS of the desired claim, right-multiply by $b$ and add $b^{k+1}a$: from there you want to rearrange to make it the RHS with $k+1$. In order to do this, split and reindex and incorporate
$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}.$$
