2
votes
2answers
113 views

Most unusual form of mathematical induction

After reading the algebraic proof of Fundamental Theorem of Algebra, where induction was carried out on "The highest power of $2$ dividing $n$", which I regard to be unusual and brilliant at the same ...
0
votes
1answer
71 views

What is the first proof that you've done using induction?

Right now in class I'm learning induction and I'm having a hard time to grasp the concepts of it, especially strong induction which confuses me even further. But out of curiosity, what is the first ...
3
votes
2answers
115 views

Equality such that induction step is valid but basis is not?

I always puzzled why the two steps are so different in complexity: almost for any proof checking the basis assertion is simple mechanical procedure, while most of the work deferred to proving ...
29
votes
17answers
5k views

Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ ...
28
votes
7answers
1k views

Must we use induction to prove a statement for all integers

This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction. From Bill's answer: A proof that a ...
1
vote
1answer
320 views

Infinite induction “valid”

As you may know, induction works only when we have a statement involving natural numbers. For instance, For every $n$, the intersection of $n$ open sets is open. Now, the corresponding statement for ...
3
votes
4answers
322 views

A resource of exercises about induction and combinatorics

I'm looking for a book, webpage or similar resource with a lot of exercises about induction and combinatorics at basic level.
15
votes
5answers
828 views

What are some examples of induction where the base case is difficult but the inductive step is trivial?

According to Wikipedia: ...proofs by mathematical induction have two parts: the "base case" that shows that the theorem is true for a particular initial value such as n = 0 or n = 1 and ...
8
votes
1answer
273 views

When can we say that a theorem has been proven?

I'm taking a Data Structures and Algorithms course for a CS program. The introductory material was all mathematics, mostly a series of formulas that we are to remember. I can work through the formulas ...