I'm guessing that this is more of a metalogic question; I am not very familiar with this area so I apologize if the terminology is lackluster.
As I advance through my math curriculum, I notice that proof by mathematical induction is becoming quite a common tool. Alternatively, I also see that the method of "arbitrary element" (not sure what the actual name is) is quite common. Only very rarely do I see examples where one can use both strategies to prove a proposition. For example, consider proving the statement that $\frac{n(n+1)}{2} = 1 + 2 + ... +n$... or, more formally:
$$f: \mathbb N \to \mathbb N$$
$$f(n) = \frac{n(n+1)}{2}$$
$$g: \mathbb N \to \mathbb N$$
$$g(n) = \sum_{i=1}^{n}i$$
$$\forall n \big(n \in \mathbb N \land n\geq 1 \implies f(n)=g(n)\big)$$
There is the traditional proof by induction (which is widely available)...but can be found on the website here: Proving the sum of the first $n$ natural numbers by induction
Then there is the method of "arbitrary element" which could be described as follows:
Choose an arbitrary element $n^*$.
Consider $g(n^*) = 1 + 2 + ... n^*$
Multiply this by $2$ and, for illustrative purposes, strategically arrange the sum as follows:
$2g(n^*)= \big (\color{blue}{1}+\color{green}{2}+...\color{red}{n^*} \big) + \big( \color{blue}{n^*}+\color{green}{n^*-1}+...+\color{red}{1} \big) = n^*(n^*+1)$
$g(n^*) = \frac{n^*(n^*+1)}{2}$
As demonstrated above, the proposition $\forall n \big(n \in \mathbb N \land n\geq 1 \implies f(n)=g(n)\big)$ can be proven both ways. However, I find that this seems to be a rare quality...or at least the ease with which one can find both methods seems to vary from proposition to proposition.
So my question is the following: If one can find success with a proof by induction argument for a given proposition, must there exist an "arbitrary element" argument for that same proposition? Similarly, if one can find success with an "arbitrary element" argument for a proposition, must there exist a proof by induction argument?
The two strategies seem fundamentally "different"...i.e. you could not assign each step a symbol in the arguments and form some sort of mapping strategy between each symbol to say that the arguments are actually the "same".
Thanks!
First, the 'arbitrary element' proof is better known as a universal proof.
And yes, if there is an inductive proof, then there is always a universal proof, and vice versa. It is just that there may not be a 'nice' or 'elegant' proof of the 'other' kind.
But yes, here is a trivial way to turn any univesl proof into an inductive proof (warning: it's going to be a 'groaner'!):
Simply define $P(n)$ to be the very claim $P$ that you are trying to prove, i.e. that you have already proven by the universal proof. Then the inductive proof is:
Base: First, we'll show that $P(0)$ is true. Well, $P(0)$ is just $P$, and we have a nice universal proof for $P$. Check!
Step: Assume that $P(n)$ is true. Well, $P(n)$ is simply $P$. But $P(n+1)$ is $P$ as well, and so we have shown $P(n+1)$. Check!
Ok, so now we have shown $\forall n P$. But since $P$ has no free variable $n$, that is simply the same as $P$, and so we are done.
Ok, so now let's (equally groanworthy!) transform any inductive proof of $P$ into a universal proof that $P$. Well, take any arbitrary number $n$. By the inductive proof, we can show $P$. Since $n$ was arbitrary, that means $\forall n P$. But since $P$ has no free variables $n$, that means $P$. Done.