Select your language

Suggested languages for you:
Log In Start studying!
StudySmarter - The all-in-one study app.
4.8 • +11k Ratings
More than 3 Million Downloads
Free
|
|

All-in-one learning app

  • Flashcards
  • NotesNotes
  • ExplanationsExplanations
  • Study Planner
  • Textbook solutions
Start studying

Proof by Induction

Proof by Induction

If a domino falls in a chain, the next domino will surely fall too. Since this second domino is falling, the next one in the chain will certainly fall as well. Since this third domino is falling, the fourth will fall too, and then the fifth, and then the sixth, and so on. Therefore, if it is known that a domino falling will knock over the next domino in the chain, you can say for a fact that knocking over the first domino in the chain will cause all the dominoes to fall. This resembles a type of mathematical proof called proof by induction.

Proof By Induction Dominos falling to illustrate how induction works StudySmarterDominos work in a similar way to proof by induction: if a domino falls, the next will fall. If you push the first domino, you can be sure all the dominos will fall.

What is Proof By Induction?

Proof by induction is a way of proving that something is true for every positive integer.

Proof by induction is a way of proving that a certain statement is true for every positive integer \(n\). Proof by induction has four steps:

  1. Prove the base case: this means proving that the statement is true for the initial value, normally \(n = 1\) or \(n=0.\)
  2. Assume that the statement is true for the value \( n = k.\) This is called the inductive hypothesis.
  3. Prove the inductive step: prove that if the assumption that the statement is true for \(n=k\), it will also be true for \(n=k+1\).
  4. Write a conclusion to explain the proof, saying: "If the statement is true for \(n=k\), the statement is also true for \(n=k+1\). Since the statement is true for \(n=1\), it must also be true for \(n=2\), \(n=3\), and for any other positive integer."

Proof by induction is an incredibly useful tool to prove a wide variety of things, including problems about divisibility, matrices and series.

Examples of Proof By Induction

First, let's look at an example of a divisibility proof using induction.

Prove that for all positive integers \(n\), \(3^{2n+2} + 8n -9 \) is divisible by 8.

Solution

First define \(f(n) = 3^{2n+2} + 8n -9 \).

Step 1: Now consider the base case. Since the question says for all positive integers, the base case must be \(f(1)\). You can substitute \(n=1\) into the formula to get

\[ \begin{align} f(1) = 3^{2+2} + 8 - 9 & = 3^4 - 1 \\ & = 81 - 1 \\ & = 80. \end{align} \]

80 is clearly divisible by 10, hence the condition is true for the base case.

Step 2: Next, state the inductive hypothesis. This assumption is that \(f(k) = 3^{2k + 2} + 8k - 9 \) is divisible by 8.

Step 3: Now, consider \(f(k+1)\). The formula will be:

\[ \begin{align} f(k+1) & = 3^{2(k+1)+2} + 8(k + 1) - 9 \\ & = 3^{2k + 4} + 8k + 8 -9 \\ & = 3^{2k+4} + 8k -9 + 8. \end{align} \]

It may seem weird to write it like this, without simplifying the \(8-9\) to become \(-1\). There is a good reason to do this: you want to keep the formula as similar to the formula of \(f(k)\) as you can since you need to transform it into this somehow.

To do this transformation, notice that the first term in \(f(k+1) \) is the same as the first term in \(f(k)\) but multiplied by \(3^2 = 9\). Hence, you can split this up into two separate parts.

\[ \begin{align} f(k+1) & = 9 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = 3^{2k+2} + 8 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = (3^{2k+2} + 8k -9) + 8 \cdot 3^{2k+2} + 8 \\ & = f(k) + 8 \cdot 3^{2k+2} + 8. \end{align} \]

The first term in this is divisible by 8 because of the assumption, and the second and third terms are multiples of 8, thus they are divisible by 8 too. Since this is the sum of different terms that are all divisible by 8, \(f(k+1)\) must also be divisible by 8 too, assuming the inductive hypothesis is true. Hence, you have proven the inductive step.

Step 4: Finally, remember to write the conclusion. This should sound something like:

If it is true that \( f(k) \) is divisible by 8, then it will also be true that \(f(k+1) \) is divisible by 8. Since it is true that \(f(1)\) is divisible by 8, it is true that \(f(n)\) is divisible by 8 for all positive integers \(n\).

In the next sections, you will look at using proof by induction to prove some key results in Mathematics.

Proof by Induction Involving Inequalities

Here is a proof by induction where you must use trigonometric identities to prove an inequality.

Prove that for any non-negative integer \(n\),

\[ |\sin{(nx)}| \leq n \sin{x}, \]

for \( x \in (0, \pi) \).

Solution

Step 1: The base case is clear, since substituting in \(n=1\) makes the inequality \( |\sin{x}| \leq{\sin{x}}\), which is true for \( x \in (0, \pi) \).

Step 2: For the induction hypothesis, assume that \[ | \sin{(mx)} | \leq m \sin{x}. \]

Step 3: You must now prove that \( |\sin{((m+1)x)}| \leq (m+1) \sin{x}. \) First, you can expand the bracket of the left hand side:

\[ |\sin{((m+1)x)}| = |\sin{(mx + x)}| \]

Now, you can use the trigonometric sum of angles formula for the sine function.

\[ |\sin{((m+1)x)}| = |\sin{(mx)} \cos{(m)} + \cos{(mx)} \sin{(m)}|. \]

From here, you can use the triangle inequality for absolute values: \( | a + b| \leq |a| + |b| \).

\[ |\sin{((m+1)x)}| \leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}|. \]

Remember that \( \cos{(mx)} \) and \( \cos{(x)} \) are less than one. Hence, you can create a new upper bound by estimating the cosine functions as 1:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}| \\ &\leq |\sin{(mx)}| + |\sin{(x)}|. \end{align} \]

From here, notice that there is \( |\sin{(mx)}| \) on the left-hand side. This is where you can use the inductive hypothesis. You know \( |\sin{(mx)}| \leq m \sin{x}\), so you can create another upper bound:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)}| + |\sin{(x)}| \\ &\leq m \sin{(x)} + |\sin{(x)}|. \end{align} \]

Finally, as was stated in the base case, \( |\sin{(x)}| \leq \sin{(x)} \). S,

\[ |\sin{((m+1)x)}| \leq m \sin{(x)} + \sin{(x)} = (m+1)\sin{(x)}, \]

as required.

Step 4: Finally, state the conclusion. We have proved that the inequality holds for \( n = m+1 \) if it holds for \( n = m.\) Since it holds for \(n=1\), by induction it will hold for all positive integers.

Proof of the Fundamental Theorem of Arithmetic by Strong Induction

The Fundamental Theorem of Arithmetic states that every integer \(n \geq 2\) can be written uniquely as a product of primes. This proof splits into two parts:

  • Proof that any integer \(n \geq 2\) can be written as a product of primes, and

  • Proof that this product of primes is unique (up to the order in which the primes are written).

The first part can be proved using a specific type of induction called strong induction.

Strong Induction is the same as regular induction, but rather than assuming that the statement is true for \(n=k\), you assume that the statement is true for any \(n \leq k\). The steps for strong induction are:

  1. The base case: prove that the statement is true for the initial value, normally \(n = 1\) or \(n=0.\)
  2. The inductive hypothesis: assume that the statement is true for all \( n \le k.\)
  3. The inductive step: prove that if the assumption that the statement is true for \(n \le k\), it will also be true for \(n=k+1\).
  4. The conclusion: write: "If the statement is true for all \(n \le k\), the statement is also true for \(n=k+1\). Since the statement is true for \(n=1\), it must also be true for \(n=2\), \(n=3\), and for any other positive integer."

Let's use strong induction to prove the first part of the Fundamental Theorem of Arithmetic.

Prove that any integer \(n \geq 2\) can be written as a product of primes.

Solution

Step 1: First, prove the base case, which in this case requires \(n=2\). Since \(2 \) is already a prime number, it is already written as a product of primes, and hence the base case it true.

Step 2: Next, state the inductive hypothesis. You will assume that for any \( 2 \leq n \leq k\), \(n\) can be written as a product of primes.

Step 3: Finally, you must use the assumption to prove that \(n=k+1 \) can be written as a product of primes. There are two cases:

  • \(k+1\) is a prime number, in which case it is clearly already written as the product of primes.
  • \(k+1\) is not a prime number and there must be a composite number.

If \(k+1\) is not a prime number, this means it must be divisible by a number other than itself or 1. This means there exists \(a_1\) and \(a_2\), with \(2 \le a_1\) and \(a_2 \le k\), such that \(k+1 = a_1 a_2. \) By the inductive hypothesis, \(a_1\) and \(a_2\) must have a prime decomposition, since \(2 \le a_1\) and \(a_2 \le k\). This means there exist prime numbers \( p_1,\dots ,p_i\) and \(q_1,\dots ,q_j\) such that

\[ \begin{align} a_1 & = p_1\dots p_i \\ a_2 & = q_1 \dots q_j. \end{align} \]

Finally, since \(k+1 = a_1 a_2, \) you have:

\[ k+1 = p_1\dots p_i q_1\dots q_j \]

which is a product of primes. Hence, this is a prime decomposition for \(k+1\).

Step 4: \(k+1\) will have a prime decomposition if all numbers \(n\), \(2 \leq n \leq k \) also have a prime decomposition. Since 2 has a prime decomposition, therefore by induction every positive integer greater than or equal to 2 must have a prime decomposition.

The proof that this product of primes is unique is a bit different, but nothing too complex. It uses proof by contradiction.

Prove that the prime factorisation for any number \(n \geq 2\) is unique.

Solution

Suppose you have two different prime factorisations for \(n\). These will be

\[ \begin{align} n & = p_1\dots p_i \mbox{ and }\\ n & = q_1\dots q_j. \end{align} \]

You can set these as equal since they both equal \(n\):

\[ p_1\dots p_i = q_1\dots q_j \]

Since the left-hand side has the factor \( p_1 \) in it, both sides must be divisible by \(p_1\). Since \(p_1\) is prime and all the \(q\)'s are also prime, it must be that one of the \(q\)'s is equal to \(p_1\). Call this \(q_k\). Now, you can cancel out \(p_1\) and \(q_k\) to get:

\[ p_2\dots p_i = q_1\dots q_{k-1} q_{k+1}\dots q_j. \]

You can do this same process with the \(p_2\), and then the \(p_3\), until you run out of either \(p\)'s or \(q\)'s. If you run out of \(p\)'s first, the left-hand side will now be 1. This means the right-hand side must be equal to 1 as well, but since it is made only of primes, it must mean that all of the primes have been cancelled out. Thus, for every \(p\) in the list, there must be a \(q\) that it is equal to. Hence, the two factorisations were in fact the same.

The process is the same if you assume that you run out of \(q\)'s first.

Proof by Induction of the Sum of Squares

The sum of the squares of the first \(n\) numbers is given by the formula:

\[ 1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

Let's prove this by induction.

Prove that for any positive integer \(n\),

\[ 1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

Solution

Step 1: First, consider the base case, when \(n=1\). The left-hand side is clearly just 1, while the right-hand side becomes

\[ \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1. \]

Hence, the base case is correct.

Step 2: Next, write the induction hypothesis. This is that

\[ 1^2 + \dots + m^2 = \frac{m(m+1)(2m+1)}{6}. \]

Step 3: Finally, prove the inductive step. The left-hand side, for \(n=m+1\), will be:

\[ 1^2 +\dots + m^2 + (m+1)^2 = (1^2 +\dots + m^2) + (m+1)^2. \]

The first \(n\) terms in this are in the inductive hypothesis. Thus, you can replace these with the right-hand side from the inductive hypothesis:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{m(m+1)(2m+1)}{6} + (m+1)^2 \\ & = \frac{m(m+1)(2m+1) + 6(m+1)^2}{6} \\ & = \frac{(m+1)\left[m(2m+1) + 6(m+1)\right]}{6}. \end{align}\]

Next, expand the bit inside of the square brackets, so you will have a quadratic. Then you can solve the quadratic normally:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{(m+1)\left[2m^2+1m + 6m+6\right]}{6} \\ & = \frac{(m+1)[2m^2 + 7m + 6}{6} \\ & = \frac{(m+1)(m+2)(2m+3)}{6} \\ & = \frac{(m+1)((m+1)+1)(2(m+1)+1)}{6}, \end{align}\]

as required. Thus, you have proven the inductive step.

Step 4: Finally, write the conclusion. If the sum of squares formula is true for any positive integer \(m\), then it will be true for \(m+1\). Since it is true for \(n=1\), it is true for all positive integers.

Proof of Binet's Formula by Induction

Binet's Formula is a way of writing the Fibonacci numbers in a closed form expression.

Binet's Formula:

\[F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, \]

where \(F_n\) is the \(n\)th Fibonacci number, meaning \(F_n\) satisfies the recurrence initial value problem:

\[ \begin{align} &F_n = F_{n-1} + F_{n-2}, \\ &F(0) =0, \\ &F(1)=1. \end{align} \]

The number \(\phi\) is known as the golden mean, and is the value:

\[\phi = \frac{1+\sqrt{5}}{2}\]

and \(\hat{\phi} = 1 - \phi.\)

Proof By Induction Fibonacci Spiral StudySmarterFig 1 - The Fibonacci numbers are a sequence of numbers, where the next number is equal to the previous two numbers added together.

Notice that \( \phi\) and \( \hat{\phi} \) are the solutions to the quadratic equation \( x^2 = 1 + x.\) This result is very important the the proof below.

Prove Binet's Formula using induction.

Solution

Step 1: First, prove the induction base. This will be for \(F_0\) and \(F_1\). For \(F_0\):

\[\frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1-1}{5} = 0, \]

which is the value of \( F_0\) as expected.

For \(F_1\):

\[ \begin{align} \frac{\phi - \hat{\phi}}{\sqrt{5}} & = \frac{\frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2}}{\sqrt{5}} \\ & = \frac{1}{\sqrt{5}}\cdot \frac{1-1 +\sqrt{5} + \sqrt{5}}{2} \\ & = 1, \end{align} \]

which is the expected answer. Thus, the induction base is proven.

Step 2: Next, state the induction hypothesis. In this case, strong induction must be used. The hypothesis is that for any \( 0 \leq i \leq k+1, \)

\[ F_i = \frac{\phi^i + \hat{\phi}^i}{\sqrt{5}}. \]

Step 3: Now you must prove the induction step, which is that

\[F_{k+2} = \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}}.\]

Start with the right-hand side and try and simplify it until you reach the left-hand side. First, start by splitting the power of \(k+2\) into 2 separate terms, one with the power of \(k\) and the other with the power of \(2\).

\[ \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} = \frac{\phi^2 \phi^k + \hat{\phi}^2 \hat{\phi}^k}{\sqrt{5}} \]

Now, you can use the result that \( \phi^2 = 1 + \phi\) and \( \hat{\phi}^2 = 1 + \hat{\phi} \).

\[ \begin{align} \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} & = \frac{(1+\phi) \phi^{k} + (1+\hat{\phi}) \hat{\phi}^{k}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k} + \phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = F_k + F_{k+1} \\ & = F_{k+2}. \end{align} \]

And thus, the induction step has been proved. The step that gets the answer to \( F_k + F_{k+1} \) requires the use of the induction hypothesis to get there.

Step 4: Finally, the conclusion: If Binet's Formula holds for all non-negative integers up to \(k+1\), then the formula will hold for \(k+2\). Since the formula holds for \(F_0\) and \(F_1\), the formula will hold for all non-negative integers.

Proof by Induction - Key takeaways

  • Proof by induction is a way of proving that something is true for every positive integer. It works by showing that if the result holds for \(n=k\), the result must also hold for \(n=k+1\).
  • Proof by induction starts with a base case, where you must show that the result is true for it's initial value. This is normally \( n = 0\) or \( n = 1\).
  • You must next make an inductive hypothesis, which is assuming that the result holds for \(n=k\). In strong induction, the inductive hypothesis is that the result holds for all \( n \leq k.\)
  • You must next prove the inductive step, showing that if the inductive hypothesis holds, the result will also hold for \( n = k+1\).
  • Finally, you must write a conclusion, explaining why the proof works.

References

  1. Fig 1: Fibonacci Spiral over tiled squares (https://commons.wikimedia.org/wiki/File:Fibonacci_Spiral.svg) by Romain, licensed by CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/?ref=openverse#).

Frequently Asked Questions about Proof by Induction

A proof by induction is done by first, proving that the result is true in an initial base case, for example n=1. Then, you must prove that if the result is true for n=k, it will also be true for n=k+1. Then, since it is true for n=1, it will also be true for n=2, and n=3, and so on. 

Proof by mathematical induction is a type of proof that works by proving that if the result holds for n=k, it must also hold for n=k+1. Then, you can prove that it holds for all positive integer values of n simply by proving that it is true for n=1. 

Proof by induction works because you are proving that if the result holds for n=k, it must also hold for n=k+1. Hence, if you show it is true for n=1, it must be true for:

  • 1+1 = 2,
  • 2+1 = 3,
  • 3+1 = 4 etc. 

The most basic example of proof by induction is dominoes. If you knock a domino, you know the next domino will fall. Hence, if you knock the first domino in a long chain, the second will fall, which will knock the third, and so on. Hence, you have proved by induction that all dominoes will fall.

The first real use of proof by induction was by the mathematician Gersonides (1288, 1344). Less rigorous techniques using mathematical induction had been used long before him however, the earliest example dating back to Plato in 370 BC. 

Final Proof by Induction Quiz

Question

What is the first step of proof by induction?

Show answer

Answer

Proving the base case.

Show question

Question

What is the second step of proof by induction?

Show answer

Answer

Forming the induction hypothesis.

Show question

Question

What is the third step of proof by induction?

Show answer

Answer

Proving the induction step. 

Show question

Question

What is the fourth step of proof by induction?

Show answer

Answer

Writing the conclusion. 

Show question

Question

What is strong induction?

Show answer

Answer

A type of mathematical induction where the induction hypothesis is: 

"Assume true for all  \(n \leq m\)"

instead of 

"Assume true for \(n = m\)".

Show question

Question

Can the following formula be proved by induction?


L'Hopital's Rule:

if \( \lim\limits_{x \rightarrow c}  f(x)\) and \( \lim\limits_{x \rightarrow c}  g(x) \) are both equal to 0 or \(\infty,\) then

\[ \lim\limits_{x \rightarrow c} \frac{f(x)}{g(x)} = \lim\limits_{x \rightarrow c} \frac{f'(x)}{g'(x)}. \]

Show answer

Answer

No.

Show question

Question

Can the following formula be proved by induction: 

For all natural numbers \(n\),

\[ 1 + ... + n = \frac{n(n+1)}{2}. \] 

Show answer

Answer

Yes.

Show question

Question

What is proving the base case of induction?

Show answer

Answer

Proving that the result is true for the first value of \(n\) in the sequence. This is usually \(n=0\) or \(n=1\). 

Show question

Question

What is the inductive hypothesis in standard induction?

Show answer

Answer

Assuming that the result holds for \(n=k.\) 

Show question

Question

What is the inductive hypothesis in strong induction?

Show answer

Answer

Assuming that the result holds for all \(n \leq k.\)

Show question

Question

What is the inductive step?

Show answer

Answer

Proving that if the inductive hypothesis holds, the result will also hold for \(n = k+1.\) 

Show question

Question

What should the conclusion say in regular induction, if the base case is \(n=0\)?

Show answer

Answer

If the result holds for \(n=k,\) it will also hold for \(n=k+1.\) Since the result holds for \(n=0,\) the result will hold for all non-negative integers \(n.\)

Show question

Question

What should the conclusion say in strong induction, if the base case is \(n=1\)?

Show answer

Answer

If the result holds for all \(n \leq k,\) the result will hold for \( n = k+1.\) Since the result holds for \(n = 1,\) it is true for all natural numbers \(n.\)

Show question

Question

What can prove by induction be used for?

Show answer

Answer

To prove formulas that hold for sequences of numbers, such as for every natural number \(n.\) 

Show question

Question

Can the following statement be proved by induction?

\( 2^n \geq n, \forall n \in \mathbb{n}. \)

Show answer

Answer

Yes.

Show question

Question

What is the first step of proving that \(f(n)\) is divisible by \(p\) for any positive integer?

Show answer

Answer

Prove that \(f(1)\) is divisible by \(p\). 

Show question

Question

What is the first step of proving that \(f(n)\) is divisible by \(p\) for any non-negative integer?

Show answer

Answer

Prove that \(f(0)\) is divisible by \(p\). 

Show question

Question

What is the first step of proving that \(f(n)\) is divisible by \(p\) for any positive odd integer?

Show answer

Answer

Prove that \(f(1)\) is divisible by \(p\).

Show question

Question

What is the first step of proving that \(f(n)\) is divisible by \(p\) for any positive even integer?

Show answer

Answer

Prove that \(f(2)\) is divisible by \(p\).

Show question

Question

What is the first step of proving that \(f(n)\) is divisible by \(p\) for any non-negative even integer?

Show answer

Answer

Prove that \(f(0)\) is divisible by \(p\).

Show question

Question

What is the inductive hypothesis when proving that \(f(n)\) is divisible by \(p\).

Show answer

Answer

Assuming that \(f(k)\) is divisible by \(p\).

Show question

Question

What is the inductive step when proving that \(f(n)\) is divisible by \(p\) for any positive integer \(n\)?

Show answer

Answer

Proving that \(f(k+1)\) is divisible by \(n\).

Show question

Question

What is the inductive step when proving that \(f(n)\) is divisible by \(p\) for any even positive integer \(n\)?

Show answer

Answer

Proving that \(f(k+2)\) is divisible by \(n\). 

Show question

Question

What is the inductive step when proving that \(f(n)\) is divisible by \(p\) for any odd positive integer \(n\)?

Show answer

Answer

Proving that \(f(n+2)\) is divisible by \(p\). 

Show question

Question

What should the conclusion say when proving that \(f(k)\) is divisible by \(p\) for any positive integer \(n\)?

Show answer

Answer

If \(f(k)\) is divisible by \(p\), \(f(k+1)\) will also be divisible by \(p\). Since \(f(1)\) is divisible by \(p\), by induction \(f(n)\) will be divisible by \(p\) for any positive integer \(n\).

Show question

Question

What should the conclusion say when proving that \(f(k)\) is divisible by \(p\) for any positive odd integer \(n\)?

Show answer

Answer

If \(f(k)\), where \(k\) is an odd integer, is divisible by \(p\), \(f(k+2)\) (the next odd integer) will also be divisible by \(p\). Since \(f(1)\) is divisible by \(p\), by induction \(f(n)\) will be divisible by \(p\) for any positive integer \(n\).

Show question

Question

What should the conclusion say when proving that \(f(k)\) is divisible by \(p\) for any positive even integer \(n\)?

Show answer

Answer

If \(f(k)\), where \(k\) is an odd integer, is divisible by \(p\), \(f(k+2)\) (the next odd integer) will also be divisible by \(p\). Since \(f(1)\) is divisible by \(p\), by induction \(f(n)\) will be divisible by \(p\) for any positive integer \(n\).

Show question

Question

What would the inductive base be when proving that 

\(f(n) = 10^n + 7^n + 4^n.\)

is divisible by 3 for any non-negative integer \(n\)?



Show answer

Answer

\(f(0) = 1 + 1 + 1 = 3\) which is clearly divisible by 3. 

Show question

Question

When can you split \(6^k\) into \(6 \cdot 6^{k+1}.\)?

Show answer

Answer

When the base step is for a value greater than or equal to 1. 

Show question

60%

of the users don't pass the Proof by Induction quiz! Will you pass the quiz?

Start Quiz

Discover the right content for your subjects

No need to cheat if you have everything you need to succeed! Packed into one app!

Study Plan

Be perfectly prepared on time with an individual plan.

Quizzes

Test your knowledge with gamified quizzes.

Flashcards

Create and find flashcards in record time.

Notes

Create beautiful notes faster than ever before.

Study Sets

Have all your study materials in one place.

Documents

Upload unlimited documents and save them online.

Study Analytics

Identify your study strength and weaknesses.

Weekly Goals

Set individual study goals and earn points reaching them.

Smart Reminders

Stop procrastinating with our study reminders.

Rewards

Earn points, unlock badges and level up while studying.

Magic Marker

Create flashcards in notes completely automatically.

Smart Formatting

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.