Finding the $n$th number on a sequence We define $S(i)=2^i-S(i-1)$ and we know that $S(0)=0$. Is it possible to derive a non recursive formula for $S(i)$?
 A: By an educated guess, divide the recurrence by $2^i$ and define $T(i):=S(i)/2^i$. Then
$$T(i)=1-\frac{T(i-1)}2.$$
The homogeneous solution (equation $T(i)=-T(i-1)/2$) is obviously $T(i)=c/(-2)^i$, and a particular solution of the non-homogeneous equation is $T(i)=2/3$. So with the initial condition $T(0)=0$
$$T(i)=\frac23(1-(-2)^{-i})$$ and
$$S(i)=\frac23(2^i-(-1)^i).$$

Alternatively, set $T(i)=(-1)^iS(i)$ so that the equation becomes
$$T(i)=T(i-1)+(-2)^i$$
so that the solution is by recurrence
$$T(i)=T(0)+\sum_{k=1}^{i-1}(-2)^k.$$
A: The most easy way to find the closed form is just to start writing the first members of te sequence down till you see a pattern:
\begin{align}
S(1)=&2\\
S(2)=&2^2-2\\
S(3)=&2^3-(2^2-2)=2^3-2^2+2\\
S(4)=&2^4-(2^3-(2^2-2))=2^4-2^3+2^2-2\\
\end{align}
Now you note that your sequence might be $S(n)=\sum\limits_{k=0}^{n-1}(-1)^{k}2^{n-k}$. I hope you know the closed form of this sum:
\begin{align} S(n)=2^n\sum\limits_{k=0}^{n-1}(-\frac 1 2)^k=2^n\frac{1-(-\frac1 2)^{n}}{1-(-\frac 1 2)}=\frac{1}{3}2^{n+1}(1-(-\frac 1 2)^{n})=\frac1 3 2^{n+1}-\frac 2 3 (-1)^{n}\end{align}
Now you have this, you can prove it by induction. I hope this helps.
A: HINT: $$S(i)=2^i-S(i-1)$$ $$S(i-1)=2^{i-1}-S(i-2)$$ $$S(i-2)=2^{i-2}-S(i-3)$$ $$\ldots$$ $$S(1)=2^1-S(0)$$
Hope it is clear now.
A: Sloane's A078008 gives $S(n)=\tfrac{1}{3}(2^{n+1} + 2\, (-1)^{n+1})$.
We can check it's true for $n=0$.  Now assume it's true for $n=k-1$ for some $n \geq 1$.  Then
\begin{align*}
S(n) &= 2^n-S(n-1) \\
 &= 2^n-\tfrac{1}{3}(2^n + 2\, (-1)^n) \\
 &= \tfrac{1}{3}(3 \cdot 2^n - 2^n - 2\, (-1)^n) \\
 &= \tfrac{1}{3}(2^{n+1} + 2\, (-1)^{n+1}).
\end{align*}
Thus verifying this formula by induction.
A: $S(i)=\frac{-2}{3}((-1)^i-2^i)$
