Prove by induction that $G(n)=2^n$

Question

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)$.

Answer 1

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$

Answer 2

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}$

Answer 3

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}$$