My book has the following proof by induction:
My confusion is with regards to the criteria that $1/3+1/c \leq 1$. Why is that required? I thought that if $(1/3+1/c)c\geq 1$ (from the second last line of the proof) then that shows that $\sum_{k=0}^{n+1}3^k = O(3^{n+1})?$
On
The claim is that for some constant $C>0$, $$\Big|\sum^n_{j=0}3^j\Big|\leq C 3^n$$ for all $n\in\mathbb{N}$.
The induct argument works fine, but this is probably best done if you try something more direct in this case. for instance, dividing by $3^n$ gives \begin{aligned} \frac{1}{3^n}\sum^n_{j=0}3^j=\sum^n_{j=0}3^{j-n}=\sum^n_{k=0}3^{-k}\leq\sum^\infty_{k=0}3^{-k}=\frac{1}{1-\frac13}=\frac32 \end{aligned} So, with $C=3/2$ one has that $\sum^n_{j=0}3^j\leq C3^n$ for all $n$.
In the induction argument you have to get the same constant at each step. (If the constant keeps changing at each step you don't know that the inequality holds for each $n$ with one fixed constant $C$ independent of $n$). Thus we have to have $(\frac 1 3 +\frac 1 c)c \leq c$. This inequality simplifies to $c \geq \frac 3 2$.