Prove by induction that $G(n)=2^n$ I have a task to solve with algorithm, which is writing all the binary numbers. I wrote the recurrence relation below, as I count the few first values:
$$G(n) = \begin{cases}1&\qquad n = 0\\
2G(n - 1)&\qquad n > 0
\end{cases}$$

I need to prove it by mathematical induction, that $G(n)=2^n$ is true for all $n>0$.

Of course, at first I counted few first values: $G(0)=1$, $G(1)=2$, $G(2)=4$, $G(3)=8$ then first step of induction: $n=1$ $L=G(1)=2 R=2G(0)=2 L=R$ second step for $n=k$ $G(k)=2G(k-1)$ And final 3rd $G(k+1)=2G(k)$. 
 A: I'm going to make a few assumptions here, as your post is not clear.
For a function $G(n)$ defined as $G(n)=\begin{cases}1\qquad\qquad\qquad n=0\\2G(n-1)\qquad n>0\end{cases}$, we want to prove that the property $P(n): G(n)=2^n$ is true for all $n\in\mathbb{N}$. We do so by (weak) induction.
Base Case
From the definition of the function, we have $G(0)=1$. As $2^n\vert_{n=0}=1$, we have $G(0)=2^0$, and $P(0)$ is true.
Inductive Hypothesis
We assume that $P(n)$ is true, i.e. $G(n)=2^n$.
Inductive Step
We obtain $G(n+1)$ from its definition, i.e. $G(n+1)=2G(n+1-1)=2G(n)$.
By hypothesis, $G(n)=2^n$, therefore $G(n+1)=2\cdot 2^n=2^{n+1}$.
Therefore $P(n+1)$ is true.
Conclusion
The property $P$ is initialized for $n=0$, and $P(n+1)$ is true if $P(n)$ is true, therefore, by the axiom of induction, $P(n)$ is true for all $n\in\mathbb{N}$. $\Box$
A: Claim : $G(n)=2^n$ for all $n\ge 0$.
Base case : $n=0$ : $2^0=1$
Induction step : $G(n+1)=2G(n)=2\times 2^n=2^{n+1}$
A: The other answers are focused on $G(n)=2^n$ (which wasn't stated). Instead I'll focus on showing that the recurrence equation is correct, and do this by induction.
Base case
The number of $0$-bit sequences is $G(0)$, where $G$ is defined as above: there is a single empty sequence and $G(0)=1$. (Actually it would be more convincing to prove the base case for $n=1$, with $G(1)=2$ sequences, namely $'0'$ and $'1'$.)
Inductive hypothesis
The number of $(n-1)$-bits sequences ($n>0$) is $G(n-1)$, where $G$ is defined as above. These sequences form a set with no duplicates and no omissions.
Inductive step
Let us take the set of $(n-1)$-bits sequences and form two new sets: one prefixing all sequences with $0$ and the other prefixing them with $1$.
By construction these sets have no duplicates and are disjoint. They also exhaust the $n$-bits sequences: indeed, taking the first bit to select the relevant set, the sequence of the remaining $n-1$ bits must be in the set as all $n-1$-bits sequences are there.
Thus, the union of the two sets is the set of all $n$-bits sequences, with no duplicates nor omissions.
Its size is clearly $2G(n-1)$, hence $G(n)=2G(n-1)$ as claimed.
Conclusion
The number of $n$-bits sequences is given by the function $G$ defined as
$$G(n) = \begin{cases}1&\qquad n = 0\\
2G(n - 1)&\qquad n > 0
\end{cases}$$
