Wednesday, May 28, 2025

Sum of 2ᵏ, or of k/(2ᵏ) for k∈ℕ∩[1,n]

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} 2+2^2+2^3+\cdots +2^n=2^{n+1}-2 \end{aligned}$$

Proof by Mathematical Induction:

We are asked to prove that for every natural number $n$,

$$ 2 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 2 $$


Step 1: Base Case

Let’s check the base case $n = 1$.

Left-hand side (LHS):

$$ 2 = 2 $$

Right-hand side (RHS):

$$ 2^{1+1} - 2 = 2^2 - 2 = 4 - 2 = 2 $$

✅ The base case holds.


Step 2: Inductive Hypothesis

Assume that the formula holds for some natural number $k$, i.e.,

$$ 2 + 2^2 + 2^3 + \cdots + 2^k = 2^{k+1} - 2 $$


Step 3: Inductive Step

We need to prove that the formula holds for $k + 1$, i.e.,

$$ 2 + 2^2 + 2^3 + \cdots + 2^k + 2^{k+1} = 2^{(k+1)+1} - 2 $$

Start from the left-hand side for $k+1$:

$$ \left(2 + 2^2 + 2^3 + \cdots + 2^k\right) + 2^{k+1} $$

Apply the inductive hypothesis to the first part:

$$ (2^{k+1} - 2) + 2^{k+1} $$

Combine like terms:

$$ 2^{k+1} + 2^{k+1} - 2 = 2 \cdot 2^{k+1} - 2 $$

Simplify the exponent:

$$ 2^{k+2} - 2 $$

Check the right-hand side formula for $k+1$:

$$ 2^{(k+1)+1} - 2 = 2^{k+2} - 2 $$

✅ Matches exactly.


Conclusion:

By the principle of mathematical induction, the formula

$$ 2 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 2 $$

holds for all natural numbers $n$.

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} \dfrac{1}{2}+\dfrac{2}{2^2}+\dfrac{3}{2^3}+\cdots +\dfrac{n}{2^n}=2-\dfrac{n+2}{2^n} \end{aligned}$$

Proof by Mathematical Induction:

We are asked to prove that for every natural number $n$,

$$ \frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \cdots + \frac{n}{2^n} = 2 - \frac{n+2}{2^n} $$


Step 1: Base Case

Check the base case $n = 1$.

Left-hand side (LHS):

$$ \frac{1}{2} = 0.5 $$

Right-hand side (RHS):

$$ 2 - \frac{1+2}{2^1} = 2 - \frac{3}{2} = 2 - 1.5 = 0.5 $$

✅ The base case holds.


Step 2: Inductive Hypothesis

Assume that the formula holds for some natural number $k$, i.e.,

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k} = 2 - \frac{k+2}{2^k} $$


Step 3: Inductive Step

Prove that the formula holds for $k + 1$, i.e.,

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} = 2 - \frac{(k+1) + 2}{2^{k+1}} $$

Start from the left-hand side for $k+1$:

Apply the inductive hypothesis to the first part:

$$ \left(2 - \frac{k+2}{2^k}\right) + \frac{k+1}{2^{k+1}} $$

Express $\frac{k+1}{2^{k+1}}$ with denominator $2^{k}$ to combine terms:

$$ 2 - \frac{k+2}{2^k} + \frac{k+1}{2^{k+1}} $$

Express $\frac{k+1}{2^{k+1}}$ as:

$$ \frac{k+1}{2 \cdot 2^{k}} = \frac{k+1}{2^{k} \cdot 2} = \frac{k+1}{2^{k+1}} $$

It doesn't directly combine, so use a common denominator $2^{k+1}$ for the fractions.

Express $2$ with denominator $2^{k+1}$:

$$ 2 = \frac{2 \cdot 2^{k+1}}{2^{k+1}} = \frac{2^{k+2}}{2^{k+1}} $$

Express $\frac{k+2}{2^k}$ with denominator $2^{k+1}$:

$$ \frac{k+2}{2^k} = \frac{2(k+2)}{2^{k+1}} $$

Now write the entire left-hand side over denominator $2^{k+1}$:

$$ \frac{2^{k+2} - 2(k+2) + (k+1)}{2^{k+1}} $$

Compute the numerator:

$$ 2^{k+2} - 2(k+2) + (k+1) $$

Compute step by step:

  • $2^{k+2}$ stays as is.
  • $-2(k+2) = -2k - 4$
  • $+(k+1)$

Sum:

$$ 2^{k+2} - 2k - 4 + k +1 = 2^{k+2} - k -3 $$

The numerator becomes:

$$ 2^{k+2} - (k +3) $$

Now express the right-hand side formula for $k+1$:

Check if it matches:

$$ 2 - \frac{(k+1)+2}{2^{k+1}} = 2 - \frac{k+3}{2^{k+1}} = \frac{2\cdot 2^{k+1}}{2^{k+1}} - \frac{k+3}{2^{k+1}} $$

Compute numerator:

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

So numerator:

$$ 2^{k+2} - (k+3) $$

Indeed, matches exactly.


Conclusion:

By the principle of mathematical induction, the formula

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{n}{2^n} = 2 - \frac{n+2}{2^n} $$

holds for every natural number $n$.

No comments:

Post a Comment