You seem to have a general confusion regarding induction, so I'll say a couple of things in the hope that somewhere in my answer is what you're looking for.
I'll put the definition a bit formally. Let's say that we want to prove some property $P(n)$ is true for all natural numbers $n$. Mathematical induction tells us that we will have proved that if we prove that:
- $P(1)$ is true
- If $P(n)$ is true for any $n$, then $P(n+1)$
You are correct that the formulas you mention are examples, not proofs. While I don't know much about the axiomatic foundations of mathematics, as far as I know you don't really prove induction. Rather, it is taken as an axiom of the natural numbers (see Peano axioms).
The problem with your statement that any integer is always one more than the one that preceded is that it's pretty much the definition of natural numbers and induction. It's not a very useful example, because you need to know that in the first place to talk about induction.
You mention that it would be sufficient, but trivial, to use your example. That's the point: why would we mention it if it's trivial? Most explanations of induction use more elaborate examples because that way they show how induction can be used to prove useful things. There is indeed something valuable in statements like "the sum of the first $n$ odd numbers is $n^2$". Namely, they are new knowledge. If we're working rigorously with natural numbers and induction, we already know that $n+1$ is one greater than $n$, because that's the basis for everything we're doing.
Let's take a look at what's wrong with your prime numbers example. First, we need to write it a bit more formally, because to use induction we need to specify $P(n)$. We could say this: $P(n)$ is the assertion that the $(n+1)$th prime number is the $n$th prime number plus one. Let's call the $n$th prime number $p_n$. Then $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, etc. $P(n)$ can now be written as $p_{n+1} - p_n = 1$.
To prove that $P(n)$ is true for all $n$, induction asks that first we prove that $P(1)$ is true. And sure enough, it's true for $n = 1$: $p_{1+1} - p_1 = 3 - 2 = 1$. So $P(1)$ is true. But the next step is where induction fails. It's not true that $P(n)$ implies $P(n+1)$. Let's say by chance we find two consecutive primes whose difference is $1$. This does not necessarily imply that it will also be true for the next pair of primes.
In terms of your analogy: we've proved that if we push the first domino it will fall, but we have not proved that if one domino falls then the next one will fall too, because in this case it's false. We can't say that if we push the first domino then all of them will fall, because we haven't proved that each domino will make the next one fall. All we know is that the first one will fall.
Regarding your definition of induction as "you can know the infinitely applicable relationship between an input and an output, so long as you have two sets of input and output from the same continuum", I must admit I don't understand it. Could you clarify what you mean with this?
Added: You seem to be confusing mathematical induction with scientific induction. In science, we can never really "prove" anything. How do we know that Einstein's relativity is true? Countless experiments and observations have been made, and every one of them agrees with relativity, so we're pretty sure it's true. But could there, in principle, be a circumstance which we haven't tested for which the law fails? Sure, and it has happened many times in the past.
Mathematical induction doesn't work this way. Say we want to prove that the sum of the first $n$ odd numbers is $n^2$. We can check for $n = 1$, and for $n = 2$, and we can check and check all day long until our calculator breaks, but we can never be sure that the statement is true for every natural number because we can't try them all. They're infinite.
Instead, (mathematical) induction provides us with a way to prove something is true for all natural numbers without individually checking all of them, something that is impossible. This is a very important point: it doesn't mean that we know something is true for a lot of numbers, so it must be true for all of them. That is false in mathematics.
When people say that there is evidence but not proof of something, that's exactly what that means. Take the Collatz conjecture, for example. Since it has been checked for a lot of numbers, most people think that it's probably right. But, and this is important again, they don't know that it's true. No one says "Well, we know the Collatz conjecture is true for $n$ up to $5000000000$, so by now we're sure it's true in general". No one says that because as long as you don't have a rigorous proof, there's always the possibility that there is an extremely high number for which the proposition fails.
Structural induction is a special case of Noetherian induction, however it doesn't seem to be clear when something is Structural induction. Vaguely the relation on the well founded set needs to be defined by some kind of recursion. Also notice that as Zhen Lin points out Noetherian induction cannot always be reduced to normal induction on the natural numbers. His example is particularly clear since the ordinals are uncountable while the natural numbers are countable.
The point of structural induction is to prove a property $P$ holds for all elements of a well founded set $S$. To do this you can assume it is not true, then there is a non-empty set $Q$ consisting of the objects that don't satisfy $P$. Since $S$ is well founded $Q$ contains a minimal element $m$. When we refer to structural induction the relation on $S$ is usually defined recursively (That is if $m<n$ if and only if $n$ can be obtained using the recursion on $m$ a finite number of times. Since $S$ is defined recursively the trick is usually to take an element $c$ smaller than $m$ and prove $m$ satisfies $P$ by using the fact $c$ satisfies $P$ and $m$ can be obtained from $c$ using the recursion. but if $c$ is in $P$ $m$ cannot be minimal, a contradiction.
Structural induction is useful when the recursion branches out into many levels and it is not very clear. For example consider the proof of the Sprague Grundy theorem, where one position $a$ is smaller than position $b$ if position $b$ is an option of position $a$
Best Answer
First, the product of all primes up to $k$, plus $1$ is not necessarily a prime number. Second, what is sometimes called Euclide's proof of the infinitude of primes numbers has two popular versions. One is a proof by contradiction and uses no induction. The other can be stated in the form of an inductive proof.
Proof by induction is a proof technique. It is essential in many many proofs of common and less common, deep as well as superficial mathematical assertions.
Mathematical induction is certainly not merely a way to give easier proofs for things you already proved in a different way. A simple example would be the proof of general associativity in a group. You must use induction (or an equivalent formulation) to prove it. Of course, it's hardly a surprising result, so you might say it is evidently true.
Mathematicians generally don't arbitrarily search for new theorems by randomly trying various proof techniques and just see what comes out. So, I wouldn't say that induction (or any other proof technique) was ever used to find a new theorem. A mathematician would use his/her intuition and understanding of a certain area to conjecture about something. Once the conjecture is in place, and was tested a bit against some examples, one might look for a proof. That proof might involve an inductive argument. Basically, anything goes when trying to find a proof.
Proof by induction typically works well when the assertion to be proved can be reduced to a similar problem which in some sense is smaller. I hope this answers your question.