- #1
gsingh2011
- 115
- 1
I understand weak induction but I'm confused on strong induction. Can someone give me a simple example where you would use strong induction and not weak?
Jarle said:Strong induction is characterized by that instead of proving P(k) --> P(k+1), where P(n) is a proposition for a number n, we rather prove that ( P(1) and P(2) and ... and P(k) )--> P(k+1). It is stronger in the sense that we use more information for the inductive step.
For example; if you want to prove a specific formula for a difference equation, say [tex]x_{n-2}+x_{x-1}=x_n[/tex], by induction, you will need, for the inductive step, that both [tex]x_{k-1}[/tex] and [tex]x_{k}[/tex] satisfy the formula in order to prove the formula for [tex]x_{k+1}[/tex]. In other words; you will need P(k-1) and P(k) to prove P(k+1), where P(n) is the proposition that [tex]x_n[/tex] satisfies the formula.
gsingh2011 said:So is this pretty much like saying you have more than one base case? Specifically, you have as many base cases as there are variables?
Strong induction is a proof technique used to show that a statement is true for all natural numbers. It differs from regular induction in that, while regular induction assumes that a statement is true for one number and then proves it is also true for the next number, strong induction assumes that a statement is true for all previous numbers and then proves it is also true for the next number.
Yes, for example, to prove that the sum of the first n even numbers is equal to n(n+1), we can use strong induction. First, we show that the statement is true for n=1, as 2=1(1+1). Then, we assume that the statement is true for all numbers up to k, so the sum of the first k even numbers is k(k+1). Using this assumption, we can show that the sum of the first k+1 even numbers is (k+1)((k+1)+1), proving the statement for all natural numbers.
Strong induction can be used to prove statements about natural numbers, such as identities, inequalities, and divisibility properties. It can also be used to prove the existence of objects, such as graphs or trees.
One limitation of strong induction is that it can only be used to prove statements about natural numbers. It cannot be used for statements about other types of numbers, such as real numbers. Additionally, strong induction may not be the most efficient proof technique for certain problems, and other methods may be more appropriate.
To improve your skills in using strong induction, it is important to practice by attempting different types of problems and proofs. You can also read and study examples of strong induction proofs to gain a better understanding of the technique. Additionally, seeking feedback and guidance from a mentor or teacher can help you improve your skills in using strong induction.