Yahoo Answers is shutting down on 4 May 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
A different kind of mathematical induction question?
When proving a result using mathematical induction the basis step (which often involves verifying the proposition for n = 0 or 1) is usually trivial. But the inductive step -- showing that if the proposition is true for n = k, then it is true for n = k+1 -- is often much more complicated.
Are there any examples of an inductive proof where the inductive step is trivial but the basis step is complicated and/or difficult?
2 Answers
- ?Lv 61 decade agoFavourite answer
There are other kinds of mathematical induction where you will find this kind of thing. For example in mathematical logic you often want to prove statements about formulas or sentences of a mathematical language. All such formulas are built from basic building blocks called terms.
For example:
x
1
3x+4
sin(xy)-8
would be terms.
Then the most basic kind of formula is an atomic formula where terms are set equal to each other or related to each other.
For example
x < 3y + 4
e^(2v) = 1 - sin(x)
would be examples of atomic formulas.
You then building more complicated formulas using:
- quantifiers: and upside down A means "for all", a backwards E means "there exists"
- Boolean connectives: V means "or", an upside down V means "and", a forward arrow means "implies", a double-headed arrow means "if and only if"
For example a sentence asserting that you are working in a universe with a less than relation which has a smallest element would be
(there exists) x (for all) y ( x = y V x < y )
Anyway the point of all of this is that when you prove statements about formulas you do it via induction on complexity, which works like this:
1. The base case is to prove it for atomic formulas.
2. You then assume it for basic formulas and prove it for formulas that add a Boolean connective or quantifier.
Most of the time the base case is much more difficult and often requires a prior lemma about terms (which often uses another induction). After that is done the inductive steps are usually pretty trivial.
- BramblyspamLv 71 decade ago
I seriously doubt it. After all, the basis step essentially amounts to plugging in a value of x into some function and then evaluating it, whereas the inductive step requires you to manipulate the function. Typically, the number to pick as your basis is very obvious from the problem too.
I have seen an example of a problem where the inductive step works (so you can prove that if the proposition is true for k then it's also true for k+1), but there is no basis k for which the problem is true.
Hope that helps!