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.
Consider the simple continued fraction $\langle a_0;a_1,a_2,\dots\rangle$, where all the $a_i$ are integers, and all positive except possibly $a_0$.
Define the sequences $p_i$, $q_i$ by
$p_{-1}=0$, $p_0=a_0$, and $p_k=a_kp_{k-1}+p_{k-2}$, and
$q_{-1}=0$, $q_0=1$, and $q_k=a_kq_{k-1}+q_{k-2}$.
We want to show that $\langle a_0;a_1,\dots,a_k\rangle=\frac{p_k}{q_k}$.
The standard way to prove the result by induction is to prove the stronger result that for any positive $x$,
$$\langle a_0;a_1,\dots,a_{k-1},x\rangle=\frac{xp_{k-1}+p_{k-2}}{xq_{k-1}+q_{k-2}}.$$
As a small additional example, a recent question asked for a proof that the denominator of
$\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}}$ can be rationalized. An induction proof used the stronger induction hypothesis that $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}+t}$ can be rationalized, where $t$ is a free parameter.
For early induction arguments, however, I think inequalities are quite persuasive, since it is clear that for example knowing that $1+\frac{1}{2^2}+\frac{1}{n^2}\lt 2$ cannot by itself imply that $1+\frac{1}{2^2}+\frac{1}{n^2}+\frac{1}{(n+1)^2}\lt 2$
Best Answer
First: I still think you can scrape some fairly simple examples/proofs by induction from that thread that you are linking, e.g tiling with trominoes or Towers of Hanoi. So carefully go through that list and there really are some suitable ones that are not too difficult
If you're doing mix of weak and strong induction, here are some of my favorites:
Number of ways $S_n$ to go up $n$ stairs where you either take $1$ or $2$ stairs at a time is a Fibonaci number, since for your first step you can either go up $1$ stairs, in which case you can do remaining $n-1$ steps in $S_{n-1}$ ways, or go up $2$ stairs, in which case you can do remaining $n-2$ steps in $S_{n-2}$ ways, so $S_n = S_{n-1} + S_{n-2}$, i.e. you're dealing with Fibonacci series. Here's a video. Make sure to first pose this question to your audience and have them struggle with it. E.g. they can figure out answer for $3$, $4$, and $5$ steps ... and then someone may actually start recognizing the Fibonacci pattern ... so then the question is: why is this so, i.e. how can we actually prove that?
What is the minimum number of breaks to break up a chocolate bar made of $m \times n$ little pieces into those very pieces?
You can first give this problem to your audience, and kind of play with them by suggesting that first making a break in the middle of the bar to get two somewhat evenly sized chunks might be a more efficient strategy than breaking off one column at a time and breaking that into little pieces one by one, since with larger chunks you can cover more individual breaklines with a single break than with smaller chunks ... But of course it doesn't matter how you do it: it will always take $n-1$ breaks to get $n$ pieces, since each break will only increase the number of chunks by one. And that insight really requires no induction, but you can use strong induction to really drive this home: first break will divide bar with $n$ pieces into a chunk with $m$ pieces and a chunk with $n-m$ pieces. By inductive assumption, the first will take $m-1$ to completely break apart, and the second takes $n-m-1$ breaks, for a total of $1 + (m-1) + (n-m-1) = n-1$ breaks.
I like these examples not only because they are visual and interactive, but also because they show that induction is not just weak mathematical induction. I see do many treatments start with weak mathematical induction and sometimes not even move on to other forms of induction, and it’s doing students a disservice because induction is a much more general concept that they should intuitively grasp rather than get lost in the formal details.
If you are looking for some more traditional algebraic weak mathematical induction ones: there is of course the sum of all numbers $1$ through $n$ ... but I would start with the algebraically somewhat simpler sum of the first $n$ odd numbers ... though both of those results have some nice proofs by picture as well which doesn't require any induction at all. Can you tell I like visuals? :P