Prove by method of induction, for all n ∈ N: 3n − 2n − 1 is divisible by 4

Question

Prove by method of induction, for all n ∈ N:

3ⁿ − 2n − 1 is divisible by 4

Sum

Solution

3ⁿ − 2n − 1 is divisible by 4 if and only if 3ⁿ − 2n − 1 is a multiple of 4.

Let P(n) ≡ 3ⁿ − 2n − 1 = 4m, where m ∈ N.

Step 1:

For n = 1, 3ⁿ − 2n − 1 = 3 − 2 − 1 = 0

which is divisible by 4.

∴ P(1) is true.

Step 2:

Let us assume that for some k ∈ N, P(k) is true,

i.e., 3^k − 2k − 1 = 4a, where a ∈ N

∴ 3^k = 4a + 2k + 1 ...(1)

Step 3:

To prove that P(k + 1) is true, i.e., to prove that

3^k+1 − 2(k + 1) − 1 is a multiple of 4,

i.e., 3^k+1 − 2(k + 1) − 1 = 4b, where b ∈ N

Now, 3^k+1 − 2(k + 1) − 1 = 3^k.3 − 2k − 2 − 1

= (4a + 2k + 1)3 − 2k − 3 ..[By (1)]

= 12a + 6k + 3 − 2k − 3

= 12a + 4k

= 4(3a + k)

= 4b, where b = (3a + k) ∈ N

∴ P(k + 1) is true.

Step 4:

From all the above steps and by the principle of mathematical induction, P(n) is true for all n ∈ N,

i.e., 3ⁿ − 2n − 1 is divisible by 4, for all n ∈ N.

shaalaa.com

Principle of Mathematical Induction

Is there an error in this question or solution?

Q 12 Q 11 Q 13

Chapter 4: Methods of Induction and Binomial Theorem - Exercise 4.1 [Page 74]

APPEARS IN

Balbharati Mathematics and Statistics (Arts and Science) Part 2 [English] Standard 11 Maharashtra State Board

Chapter 4 Methods of Induction and Binomial Theorem
Exercise 4.1 | Q 12 | Page 74

RELATED QUESTIONS

Prove the following by using the principle of mathematical induction for all n ∈ N:

1.3 + 2.3^3 + 3.3^3 +...+ n.3^n = `((2n -1)3^(n+1) + 3)/4`

Prove the following by using the principle of mathematical induction for all n ∈ N:

`1/2.5 + 1/5.8 + 1/8.11 + ... + 1/((3n - 1)(3n + 2)) = n/(6n + 4)`

Prove the following by using the principle of mathematical induction for all n ∈ N:

`1/3.5 + 1/5.7 + 1/7.9 + ...+ 1/((2n + 1)(2n +3)) = n/(3(2n +3))`

Prove the following by using the principle of mathematical induction for all n ∈ N: 3²ⁿ^{+ 2} – 8n– 9 is divisible by 8.

Prove the following by using the principle of mathematical induction for all n ∈ N (2n +7) < (n + 3)²

If P (n) is the statement "n(n + 1) is even", then what is P(3)?

If P (n) is the statement "n² − n + 41 is prime", prove that P (1), P (2) and P (3) are true. Prove also that P (41) is not true.

1 + 3 + 3² + ... + 3ⁿ⁻¹ = \[\frac{3^n - 1}{2}\]

1.2 + 2.2² + 3.2³ + ... + n.2ⁿ= (n − 1) 2ⁿ⁺¹+2

5²ⁿ⁺² −24n −25 is divisible by 576 for all n ∈ N.

(ab)ⁿ = aⁿbⁿ for all n ∈ N.

7²ⁿ + 2³ⁿ⁻³. 3ⁿ⁻¹ is divisible by 25 for all n ∈ N.

11ⁿ⁺² + 12²ⁿ⁺¹ is divisible by 133 for all n ∈ N.

Given \[a_1 = \frac{1}{2}\left( a_0 + \frac{A}{a_0} \right), a_2 = \frac{1}{2}\left( a_1 + \frac{A}{a_1} \right) \text{ and } a_{n + 1} = \frac{1}{2}\left( a_n + \frac{A}{a_n} \right)\] for n ≥ 2, where a > 0, A > 0.
Prove that \[\frac{a_n - \sqrt{A}}{a_n + \sqrt{A}} = \left( \frac{a_1 - \sqrt{A}}{a_1 + \sqrt{A}} \right) 2^{n - 1}\]

Prove that 1 + 2 + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1 for all n \[\in\] N .

\[\frac{1}{2}\tan\left( \frac{x}{2} \right) + \frac{1}{4}\tan\left( \frac{x}{4} \right) + . . . + \frac{1}{2^n}\tan\left( \frac{x}{2^n} \right) = \frac{1}{2^n}\cot\left( \frac{x}{2^n} \right) - \cot x\] for all n ∈ N and \[0 < x < \frac{\pi}{2}\]

\[\text{ A sequence } a_1 , a_2 , a_3 , . . . \text{ is defined by letting } a_1 = 3 \text{ and } a_k = 7 a_{k - 1} \text{ for all natural numbers } k \geq 2 . \text{ Show that } a_n = 3 \cdot 7^{n - 1} \text{ for all } n \in N .\]

\[\text{ A sequence } x_0 , x_1 , x_2 , x_3 , . . . \text{ is defined by letting } x_0 = 5 and x_k = 4 + x_{k - 1}\text{ for all natural number k . } \]
\[\text{ Show that } x_n = 5 + 4n \text{ for all n } \in N \text{ using mathematical induction .} \]

\[\text{ Using principle of mathematical induction, prove that } \sqrt{n} < \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + . . . + \frac{1}{\sqrt{n}} \text{ for all natural numbers } n \geq 2 .\]

Prove by method of induction, for all n ∈ N:

1² + 2² + 3² + .... + n² = `("n"("n" + 1)(2"n" + 1))/6`

Answer the following:

Prove, by method of induction, for all n ∈ N

2 + 3.2 + 4.2² + ... + (n + 1)2^n–1 = n.2ⁿ