1
$\begingroup$

I know for simple induction you generally want to use this technique when the domain of the conjecture is in the Naturals.However, direct-proof approach would sometimes work too. For example, if i were to find the max length of a path in a connected graph with n vertices, would i claim the max length is n-1 then do induction on n? On the flipside, can i just argue that the graph will at most have path of length n-1 since every consecutive vertice in path must be an edge(by definition). Thus if the graph has a cycle max path length would be less than n-1.

$\endgroup$
2
$\begingroup$

Since I'm not very knowledgeable about graph theory, I won't try to recommend which method(s) to use with your example of the "max length of a path in a connected graph with $n$ vertices".

For what it's worth though, in answer as to when to use induction or direct proof (or possibly other techniques) in general, I believe there are no hard & fast rules. Note that many (likely most) conjectures can be proven in more than one way. The "best" technique generally depends on what you know & understand, plus what seems to be simplest & easiest. However, there may be exceptions, such as if a longer & more involved technique gives a more general result that can be applied to many other situations.

Although general guidelines can be determined, or provided, as to what proof technique is best to use in various situations, I don't believe anybody can ever reasonably cover every possible case. Instead, your knowledge & experience will often help guide you in terms of how to best approach trying to solve a given problem.

Specifically regarding using induction, though, I don't fully agree with your initial statement of

I know for simple induction you generally want to use this technique when the domain of the conjecture is in the Naturals.

A more accurate statement would be that one of the first techniques you should consider using is simple induction. There are many conjectures with domains of the natural numbers where simple induction does not work, or at least does not work well, but either some other type of induction (e.g., strong) could work, or perhaps induction is not really applicable at all (e.g., for many prime, congruence, polynomial, etc., related conjectures). However, a good clue that a type of induction will likely work well is if you have some type of relation of one natural number value, defined by values at other earlier natural number(s) (e.g., a sequence value at $n$ is defined in terms of the values at $n - 1$ and $n - 2$). This will help to allow applying the required base and inductive steps (e.g., as explained in Mathematical induction).

$\endgroup$
  • $\begingroup$ I think the last two paragraphs here provide the best answer to the question = you think about the actual problem you are trying to solve - that and your experience will suggest strategies to try. Perhaps edit your answer to start out with that material. $\endgroup$ – Ethan Bolker Apr 9 at 0:54
  • $\begingroup$ @EthanBolker Thank you for your suggestion. I agree with it, so I've adjusted my answer accordingly. Please let me know if you have any other suggestions for improving my answer. $\endgroup$ – John Omielan Apr 9 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.