Prove the following statements using the Principle of Mathematical Induction: 1. 3ⁿ-1 is divisible by 2 for all n ext extgreater ext 1. 2. 2ⁿ ext extgreater ext n+1 for all n ext extgreater ext 1.

Here are the solutions to the problems using the Principle of Mathematical Induction.

1. Prove that $3^n-1$ is divisible by 2 for all $n \ge 1$.

Let $P(n)$ be the statement "$3^n-1$ is divisible by 2".

• Base Case (n=1): $P(1): 3^1-1 = 2$. Since 2 is divisible by 2, $P(1)$ is true.

• Inductive Hypothesis: Assume $P(m)$ is true for some positive integer $m$. That is, assume $3^m-1$ is divisible by 2. This means $3^m-1 = 2k$ for some integer $k$. So, $3^m = 2k+1$.

• Inductive Step: We need to prove that $P(m+1)$ is true, i.e., $3^{m+1}-1$ is divisible by 2. Consider $3^{m+1}-1$:

  $$3^{m+1}-1 = 3 \cdot 3^m - 1$$

  Substitute $3^m = 2k+1$ from the inductive hypothesis:

  $$3(2k+1) - 1$$ $$6k + 3 - 1$$ $$6k + 2$$ $$2(3k+1)$$

  Since $2(3k+1)$ is a multiple of 2, $3^{m+1}-1$ is divisible by 2. Thus, $P(m+1)$ is true.

By the Principle of Mathematical Induction, $P(n)$ is true for all $n \ge 1$.
The proof is complete.

---

2. Prove that $2^n \ge n+1$ for all $n \ge 1$.

Let $P(n)$ be the statement $2^n \ge n+1$.

• Base Case (n=1): LHS $= 2^1 = 2$ RHS $= 1+1 = 2$ Since $2 \ge 2$, $P(1)$ is true.

• Inductive Hypothesis: Assume $P(m)$ is true for some positive integer $m$. That is, assume $2^m \ge m+1$.

• Inductive Step: We need to prove that $P(m+1)$ is true, i.e., $2^{m+1} \ge (m+1)+1$, which simplifies to $2^{m+1} \ge m+2$. Consider the LHS of $P(m+1)$:

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

  By the Inductive Hypothesis, we know $2^m \ge m+1$. Multiply both sides by 2:

  $$2 \cdot 2^m \ge 2(m+1)$$ $$2^{m+1} \ge 2m+2$$

  We want to show $2^{m+1} \ge m+2$. Since $m \ge 1$, we know that $m \ge 0$. Therefore, $2m+2 = m+m+2 \ge m+0+2 = m+2$. So, we have:

  $$2^{m+1} \ge 2m+2 \ge m+2$$

  Thus, $2^{m+1} \ge m+2$. This proves $P(m+1)$ is true.

By the Principle of Mathematical Induction, $P(n)$ is true for all $n \ge 1$.
The proof is complete.