Having trouble figuring out when to use induction or direct proof.

Question

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.

Answer 1

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).