How are formulas with inductive proofs discovered?


by Avichal
Tags: discovered, formulas, inductive, proofs
Avichal
Avichal is offline
#1
Dec12-12, 10:29 PM
P: 282
There are certain formulas for which only inductive proofs are known. But since we need to know the formula first to prove it using mathematical induction, how do they get the formula in the first place?
Here is an example: - Euler's formula in graph theory states that v-e+f=2 for all planar graphs. I think only an inductive proof is currently known. So how did he come up with this formula without proving it first?...guessing?
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
Ryuzaki
Ryuzaki is offline
#2
Dec12-12, 10:51 PM
Ryuzaki's Avatar
P: 39
Here is some interesting information (courtesy of micromass):-

www.homepages.math.uic.edu/~kauffman/DCalc.pdf

www.math.upenn.edu/~wilf/gfologyLinked2.pdf

I believe the topic of generatingfunctionology answers yours question, though I'm no expert.
Vargo
Vargo is offline
#3
Dec14-12, 10:41 AM
P: 350
There are different ways.
1. Try to find a formula empirically. For example, if you want to know a formula for the nth triangular number 1+2+3+...+n, you could compute the first 20 and try to find a relationship with n by examining the numbers. You can notice a lot of patterns just be examining data closely.

2. Sometimes you can know a lot about a problem without completely understanding it. In those cases you might have reason to believe something but not be able to prove it. For example, you might suspect that ln(n) - 1 -1/2 -1/3 - ... - 1/n approaches a limit without being able to prove it. Basically, even if you don't understand something very well, you can try to apply induction. You can "get lucky" with induction by proving something that you don't understand that well. The drawback is that such proofs don't always add much to your understanding or suggest new avenues to pursue.

I suspect that empirical observation is the main way that people conjecture formulas before they understand them.

chiro
chiro is offline
#4
Dec14-12, 03:57 PM
P: 4,570

How are formulas with inductive proofs discovered?


Hey Avichal.

One should note the important step in an inductive proof which is the delta between successive values of n.

It obviously depends on the nature of the constraint (summation, multiplication, inequality, etc) but looking at the delta between steps is a good way to proving something or at least getting an idea of whether it potentially could be true (in the context of statements in induction proofs).


Register to reply

Related Discussions
Set cardinality, Turing encoding, and inductive proofs... Set Theory, Logic, Probability, Statistics 16
Assistance w/ Inductive Proofs required :-) Calculus & Beyond Homework 6
Proofs of max and min formulas for 2 numbers Precalculus Mathematics Homework 5
Proofs of fast formulas for computing constant pi General Math 4
Proofs...advice/places to find more practice proofs Introductory Physics Homework 2