For the setup, we need to assume that $a_n = 2^n - 1$ for some $n$, and then show that the formula holds for $n + 1$ instead. That is, we need to show that $$a_{n + 1} = 2^{n + 1} - 1$$
Let's just compute directly:
\begin{align*}
a_{n + 1} &= 2a_n + 1 \hspace{1.55in}\text{// recursion relation} \\
&= 2 \cdot (2^n - 1) + 1 \hspace{1in} \text{// induction hypothesis} \\
&= 2^{n + 1} - 2 + 1 \hspace{1.15in} \text{// arithmetic} \\
&= 2^{n + 1} - 1
\end{align*}
which is exactly what we wanted to be true.
This is a valid technique, though it’s a bit confusingly presented in that document. Consider the following:
$f(0,0)$ is known to be true
It is known that if $f(x,y)$ is true, then $f(x+1,y)$ is true
It is known that if $f(x,y)$ is true, then $f(x,y+1)$ is true.
We can iteratively apply the second and third line to conclude that $f(x,y)$ is true for all $(x,y)\in\mathbb N^2$. Simply use the second line to increment the $x$ value from $0$ to the desired number, and then use the third line to increment the $y$ value to the desired number.
There are many different ways you can define this type of “multivariate induction” based on how you wish to inductively pass through the set $\{f(x,y):x,y\in\mathbb N\}$. For example, another way would be to prove that:
$f(0,0)$ is true
If $f(x,y)$ is true for all $x,y$ such that $x+y=\ell$ for some $\ell\in \mathbb N$ then $f(x,y)$ is true for all $x,y$ such that $x+y=\ell+1$
This method looks a bit stranger, but has two benefits. Firstly, it more directly relates the proof to regular induction by exposing that the problem is actually about induction over $\ell$. Secondly, it passes through the set $\{f(x,y)\}$ in a way that is more natural for many problems. If you imagine $\{f(x,y)\}$ as a grid, this statement says that if all the points on the line of slope $-1$ and intercept $\ell$ satisfy the property, then all the points on the line of slope $-1$ and intercept $\ell+1$ do as well. This way of passing through your set is more natural in contexts line Pascal’s Triangle, where it lets you induct down the rows.
Your proof is doing this second sort of induction, just not in a particularly explicit way. The reason this is more natural in this context is that you don’t really care about if $n$ goes up by one vs if $m$ goes up by one, the only thing you care about is that the total exponent does.
Your argument is also valid, but it’s not an inductive argument strictly speaking. What you’re saying is:
It is known that, for arbitrary $x$, if $f(x,y)$ is true then $f(x,y+1)$ is true.
Therefore for arbitrary $x$ and all $y$, $f(x,y)$ is true.
Therefore for all $x,y$ $f(x,y)$ is true.
The step from 2 to 3 doesn’t use induction. It uses what is known in formal logic as the $\forall$-introduction rule, which is an axiom of first order logic. The connection between $\forall$I and the use of the word “arbitrary” is described in the Stanford Encyclopedia of Philosophy as follows:
This rule (∀I) corresponds to a common inference in mathematics. Suppose that a mathematician says “let n be a natural number” and goes on to show that n has a certain property P, without assuming anything about n (except that it is a natural number). She then reminds the reader that n is “arbitrary”, and concludes that P holds for all natural numbers. The condition that the variable v not occur in any premise is what guarantees that it is indeed “arbitrary”. It could be any object, and so anything we conclude about it holds for all objects.
The SEP article is a good source on introductory logic and the $\forall I$ rule, if you wish to learn more.
Best Answer
You are virtually there. The induction is really an induction on $k$ starting at $0$, to prove $T(n) = (3c/2)\cdot n - c/2$ where $n = 3^k$: For the base case:
$$T(3^0) = T(1) = c = (3c/2)\cdot 3^0 - c/2$$
For the inductive step, the inductive hypothesis is:
$$T(3^k) = (3c/2)\cdot 3^k - c/2$$
and using this and the recursive definition, you get:
$$T(3^{k+1}) = 3T(3^k) + c = 3\left[(3c/2)\cdot 3^k - c/2\right] + c= (3c/2)\cdot 3^{k+1} - c/2$$
which completes the inductive proof