maths.free › Combinatorics & Graph Theory › Induction › Proofs by Induction
Proofs by Induction
No discussion of recursion and induction would be complete without some obligatory examples of proofs using induction. We start with the Hello World example.
Proofs by Induction
No discussion of recursion and induction would be complete without some obligatory examples of proofs using induction. We start with the Hello World example.
For our first version of a proof of , we clearly identify the open statement \(S_n\) and describe the proof carefully in terms of \(S_n\). As you develop more experience with writing proofs by induction, this will become less essential, as you'll see in the second version of the proof.
Proof
Let \(n\) be a positive integer, and let \(S_n\) be the open statement \[\begin{aligned}\end{aligned}\] We will prove that \(S_n\) is true for all positive integers by induction. For the basis step, we must prove that \(S_1\) is true. When \(n=1\), the left-hand side of \(S_n\) is just \(1\), while the right-hand side evaluates to \(1(1+1)/2=1\). Therefore, \(S_1\) is true.
Next we assume that for some positive integer \(k\), \(S_k\) is true. That is, we assume \[\begin{aligned}\end{aligned}\] We now seek to prove that \(S_{k+1}\) is true, and begin by considering the left-hand side of \(S_{k+1}\). We notice that \[\begin{aligned}\end{aligned}\] since our inductive hypothesis that \(S_k\) is true gives us the simpler formula for the summation. Now continuing with a bit of algebra, we find \[\begin{aligned}\end{aligned}\] Therefore, \(S_{k+1}\) is true. Since we have shown that \(S_1\) is true and that for every positive integer \(k\), if \(S_k\) is true, then \(S_{k+1}\) is true, we conclude that \(S_n\) is true for all positive integers \(n\) by the .
Before looking at a refined version of this proof, let's take a moment to discuss the key steps in every proof by induction. The first step is the basis step, in which the open statement \(S_1\) is shown to be true. (It's worth noting that there's nothing special about \(1\) here. If we want to prove only that \(S_n\) is true for all integers \(n\geq 5\), then proving that \(S_5\) is true is our basis step.) When proving the basis step, if \(S_n\) is an equation, we do not just write down \(S_1\) and move on. We need to prove that \(S_1\) is true. Notice how in the proof above, we discussed the left-hand side of \(S_1\) and the right-hand side of \(S_1\) and concluded that they were equal.
Now let's take a look at a more refined proof of . From here on, when we give a proof by induction, we'll use this style. As you're getting started with induction proofs, you may find it useful to be more explicit about the steps as we did in the first proof above.
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
Now you Ոչ մի հաշվիչ չի կարող լուծել այս խնդիրը, բայց դրա մասերը հաշվարկելի են։ Փորձեք ստորեւ նշվածներից մեկը կամ գրեք ձեր սեփականը։
Պարզաբանում (2)
Սկզբում փորձեք յուրաքանչյուրը թղթի վրա։ Առաջին հերթին բացահայտեք պատասխանը ստուգելու համար։ Ստուգված պատասխանները կարող են բացվել յուրաքանչյուր քայլում։
-
Suppose that \(t(n)\) is a recursive function defined for \(n\geq 1\) such that \(t(1)=1\) and for \(n\geq 2\), \(t(n)=2t(n-1)+1\). Create a proof that for all \(n\geq 1\), \(t(n) = 2^n - 1\).
-
Write a couple of sentences explaining why the making the inductive hypothesis is not the same as assuming what we are trying to prove.
Ազատ հաշիվը յուրաքանչյուր դասավանդման համար գրառումներ է ավելացնում, Ձեր ավարտելիք դասերի և լուծված խնդիրների ցուցակ է պահում մեկ տեղում, և ուսուցիչ, ում կարող եք հարցնել այս էջի մասին։ Մաթեմատիկան բաց է բոլորի համար, անկախ նրանից մուտքագրվել եք արդյոք կամ ոչ։
Գրանցվել ԳրանցումՕգտագործված սիմվոլներ
Տեղադրեք ցանկացած նշան՝ ամբողջական սահմանման, նկարի և դրա մեջ ամեն մի տառի իմաստը տեսնելու համար։
Հարցեր, որոնք մարդիկ տալիս են :
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Այս էջը կառուցված է հետևյալ սկզբունքով. Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Ընդհանուր և հատուկ դասակարգումներ: Ընդհանուր դասակարգում.
Ցուցադրել Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs