Induction proof that $2^m 2^n = 2^{m+n}$

Question

I am unable to proceed with the below claim.

$$2^{m} \times 2^{n} = 2^{m+n}$$

Could anyone let me know how to prove the above claim using induction proof?

I was able to derive proof for odd natural numbers using induction but not able to do the above one.

Answer 1

Let's proceed by induction on $m+n$.

If $m+n=0$, then $m=n=0$ and $2^0\cdot2^0=1=2^{0+0}$.

If $m+n\ge1$, then WLOG $n\ge1$ and $$2^m\cdot2^n=2^m\cdot2^{n-1}\cdot2\overset{\text{IH}}=2^{m+n-1}\cdot2=2^{m+n}.$$

Answer 2

Hint:-

You may apply the method of Double Induction.

Sketch of a Solution:-

First we fix $m$ and apply induction on $n$. It will be assumed that the Induction basis is already proved because you know $2\times 2^m=2^m\times 2=2^{m+1}$.

Then assuming the statement holds for some $n$ (remember $m$ is fixed) we have,

$$2^m\times 2^n=2^{m+n}\implies 2\times\left(2^m\times > 2^n\right)=2\times\left(2^{m+n}\right)\implies \left(2^m\times > 2^{n+1}\right)=\left(2^{m+n+1}\right)$$

Can you do the same for $m$, i.e., keeping $n$ fixed apply induction on $m$.

What does proving this gives you?

Answer 3

You don't need double induction. Let $m$ be a natural number; we want to prove that, for all natural numbers $n$, $2^m\cdot 2^n=2^{m+n}$

The assertion is true for $n=0$, as $2^m\cdot2^0=2^m\cdot 1=2^m$, while $2^{m+0}=2^m$.

Suppose the assertion is true for $n$. Then $$ 2^m\cdot 2^{n+1}=2^m\cdot(2^n\cdot2)=(2^m\cdot 2^n)\cdot 2 \overset{*}{=}2^{m+n}\cdot2=2^{(m+n)+1}=2^{m+(n+1)} $$

Therefore $2^m\cdot 2^n=2^{m+n}$ for all $n$. Apply generalization, as we put no restriction on $m$.

The symbol $\overset{*}{=}$ denotes where the induction hypothesis is used. The properties used are those of multiplication and addition, together with the recursive definition of $2^k$ by

• $2^0=1$
• $2^{k+1}=2^k\cdot 2$