let $a_0 = 0, a_1=1,a_n = \frac{a_{n-1} + a_{n-2}}{2} $
prove with induction that $a_n = \frac23 \left(1 + \frac{(-1)^{n+1}}{2^n} \right) $
i assumed $a_k$ was equal to the given formula and has gotten the following equation:
$a_{k+1} =-\frac{1}{3}a_k -3$
i think that i need to prove somehow that this is always the case, but i dont know where to go from here...
In this case, you will actually need two base steps, since your recursion involves two previous terms. Also, note that your closed form should be $$a_n=\frac23\left(1+\frac{(-1)^{n+1}}{2^n}\right).\tag{$\star$}$$ Our two base cases (which I leave entirely to you) will be $n=0$ and $n=1.$
Now, for the induction step we must assume that it holds for the previous two cases--that is, suppose we have an integer $k\ge 2$ such that $(\star)$ holds for $n=k-2$ and $n=k-1.$ We must show that it holds for $n=k$.
Since $k\ge 2,$ then $$a_k=\frac12\left(a_{k-2}+a_{k-1}\right)$$ by definition, and since $(\star)$ holds for $n=k-2$ and $n=k-1,$ we then have $$a_k=\frac12\left(\frac23\left(1+\frac{(-1)^{(k-2)+1}}{2^{k-2}}\right)+\frac23\left(1+\frac{(-1)^{(k-1)+1}}{2^{k-1}}\right)\right).$$ After some arithmetic manipulations (which I leave to you), we will indeed see that $$a_k=\frac23\left(1+\frac{(-1)^{k+1}}{2^k}\right),$$ as desired.
In general, if our recursion involves multiple previous terms, then we will need multiple base cases and multiple induction hypotheses. For (a monumentally contrived) example, suppose that $b_0=0,b_1=1,b_2=2,b_3=3,b_4=4,b_5=5$ and that for $n\ge 6,$ we have $$b_n=b_{n-5}+\frac53\left(b_{n-3}-b_{n-6}\right).$$ I claim that $b_n=n$ for all $n$. Now, since the recursion doesn't start until term $6,$ then we will need $6$ base cases ($n=0$ through $n=5,$ all of which are immediate in this example). The recursion, itself, involves terms ranging from $3$ prior (at the least) through $6$ prior (at the most), so we need $6-3+1=4$ assumptions in our inductive hypothesis. In particular, we need to assume that there is some $k\ge6$ such that $b_n=n$ for $n=k-6,k-5,k-4,k-3.$ We then want to show that $b_n=n$ when $n=k$ (and possibly justify that this completes the proof). Indeed, $$b_k=b_{k-5}+\frac53\left(b_{k-3}-b_{k-6}\right)=(k-5)+\frac53\bigl((k-3)-(k-6)\bigr)=k-5+\frac53\cdot 3=k.$$ Now, since $b_0,b_1,b_3$ have the desired form, then $b_6$ is taken care of; since $b_1,b_2,b_4$ have the desired form, then $b_7$ is taken care of; since $b_2,b_3,b_5$ have the desired form, then $b_8$ is taken care of; etc. In this fashion, we see that $b_n=n$ for all integers $n\ge 0.$
You can generalize this idea to prove a closed form for any recursively defined sequence.