I had never seen the second principle of induction before, also called strong mathematical induction or complete induction, but the name suggests really all that it is: a wider variant of mathematical induction. When we use the principle of finite induction (mathematical induction), we know that a proposition ${P(n),\,\forall{n}\in\mathbb{N}}$, is true whenever there is some ${n=k}$ such that ${P(k)}$ and ${P(k+1)}$ holds and the proposition is true for the base case (usually 1). To see this is rather easy and intuitive, since it is just a generalization for all natural numbers of some particular proposition. But sometimes the assumption that ${P(k)}$ holds for ${n=k}$ is not enough and you’ve got to assume that the proposition holds for all ${n\geq{k}}$; that is, for all the elements of a subset ${A=\{n_0\in\mathbb{N}\,|\,n\geq{n_0,n_0+1,\ldots,k-1,k}\}}$ where ${n_0}$ is the base case. It often just entails proving the base case for each element.The following example, for Fibonacci numbers, illustrates the proof of a proposition by means of strong mathematical induction. The original sentence can be found in “Elements of the theory of numbers” by Joseph & Thomas Dence.
Let us assume that for ${k\leq{n}}$, the proposition ${P(k):\,F_{k+1}\leq\phi^k}$, where $\phi\equiv(1+\sqrt{5})/2$ (the golden ratio), is true; then for ${k+1}$, *
$$F_{k+2}=F_{k+1}+F_{k}\leq\phi^{k-1}(\phi+1)$$ now notice that
$$\phi+1=\frac{3+\sqrt{5}}{2}=\frac{6+2\sqrt{5}}{4}=\frac{1+2\sqrt{5}+5}{4}=\phi^2$$ so the previous inequality becomes evident as
$$F_{k+2}\leq\phi^{k+1}$$ and so ${P(k+1)}$ is also true. Hence we say that by induction ${P(n)}$ is true ${\forall{n}\in\mathbb{N}}$.
This illustrates the situation in Mathematica for continuous functions
with the command
Notice the exponential growth of the Fibonacci numbers. Now dare you to prove that ${F_{n+1}\geq\phi^{n-1},\,\forall{n}\geq{1}}$.
* This assumption is the key of the strong mathematical induction. In this problem the cases ${n=1,\ldots,k-1,k}$ are considered. Notice that for the base case ${n=1}$, each proposition holds.
The Fibonacci numbers denoted ${F_n}$ are defined recursively by ${F_1=F_2=1}$, ${F_n=F_{n-1}+F_{n-2}}$ for ${n>2}$. Show that for ${n\in\mathbb{N}}$, ${F_{n+1}\leq[(1+\sqrt{5})/2]^n}$.It can be easily verified for the base case ${n=1}$ to begin the proof.
Let us assume that for ${k\leq{n}}$, the proposition ${P(k):\,F_{k+1}\leq\phi^k}$, where $\phi\equiv(1+\sqrt{5})/2$ (the golden ratio), is true; then for ${k+1}$, *
$$F_{k+2}=F_{k+1}+F_{k}\leq\phi^{k-1}(\phi+1)$$ now notice that
$$\phi+1=\frac{3+\sqrt{5}}{2}=\frac{6+2\sqrt{5}}{4}=\frac{1+2\sqrt{5}+5}{4}=\phi^2$$ so the previous inequality becomes evident as
$$F_{k+2}\leq\phi^{k+1}$$ and so ${P(k+1)}$ is also true. Hence we say that by induction ${P(n)}$ is true ${\forall{n}\in\mathbb{N}}$.
This illustrates the situation in Mathematica for continuous functions
<<PlotLegends`
Plot[{Fibonacci[x+1], GoldenRatio^x}, {x,1,20},
Filling -> {1->{2}}, PlotStyle -> Thick,
PlotLegend -> {"F_n+1", "phi^n"},
LegendPosition -> {-0.75,0}]
* This assumption is the key of the strong mathematical induction. In this problem the cases ${n=1,\ldots,k-1,k}$ are considered. Notice that for the base case ${n=1}$, each proposition holds.
No comments:
Post a Comment