What is induction, really? I am usually confused about what is induction and what proof means in this context. As an example, take the proof of the sum of the first $n$-integers. First, we take the assertion $A_{n}$:
$$1+2+3+\dots + n\stackrel{?}{=}\frac{n(n+1)}{2}$$
Then, if $r$ is an integer and if the previous statement is true, that is:
$$1+2+3+\dots + r=\frac{r(r+1)}{2}$$
Then by adding $(r+1)$ to both sides, gives me:
$$1+2+3+\dots + r+(r+1)=\frac{r(r+1)}{2}+(r+1)=\frac{r(r+1)+2(r+1)}{2}=\frac{(r+1)(r+2)}{2}$$
Which is precisely the statement $A_{r+1}$. If we test for the statement $A_1$, it is true. Then it is true for each natural number. For this, we had the requirements: 


*

*$P(k)$ is true;

*$P(n)\implies P(n+1)$ for $n\geq k$.



Side question In this example, it is not clear why $P(n)\implies P(n+1)$, that is: Why taking $\cfrac{n(n+1)}{2}$ and $\cfrac{r(r+1)}{2}$, making the substitutions $r:=r+1$, $n:=n+1$ and comparing the formulas show the truth of $A_n$? Why couldn't we use the same trick with any other formula not equivalent to $A_n$ and a similar result, that is: Have the proof I gave earlier as true and a proof that $1+2+3+\dots +n=F_n$ but $F_n\neq \cfrac{n(n+1)}{2}$?

Now, there is another proof for the same fact, take the following figure:
\begin{matrix}
 \circ & \circ   & \circ  \\ 
 \circ & \circ   & \\ 
 \circ &  & 
\end{matrix}
Now make a rotated copy of this figure:
\begin{matrix}
 &  &\bullet    \\ 
 & \bullet &\bullet  \\ 
 \bullet &\bullet   & \bullet 
\end{matrix}
And glue them together:
\begin{matrix}
 \circ & \circ   & \circ  \\ 
 \circ & \circ   & \bullet \\ 
 \circ & \bullet   & \bullet \\
 \bullet &\bullet   & \bullet 
\end{matrix}
In any way you glue them, the side of one rectangle will be $n+1$, the other will be $n$. Now we can see that for any $n$, we must have a square of area $n(n+1)$ and we want the area of the triangle. We can just do it as $\cfrac{n(n+1)}{2}$.

Now here comes my problem: I don't actually feel that the first way proves this, but I feel that the second way does it. Also, with the first way, the formula appeared magically, we obtained it somewhere and are just proving it. But what is the actual meaning of proving here? Several months ago, I read a bit of Wittgenstein's Tractatus Logico-Philosophicus. There is an interesting item at it:
$$\text{7. Whereof one cannot speak, thereof one must remain silent.}$$
I guess that this hinted me for the first time what is the broader meaning of proving: I interpreted being able to speak as being able to say something in a given language. So in this case, it seems we are being able to speak in logic and induction is the ability to express a mathematical idea in the language of logic.  So, in the first case, we are speaking something and showing that the conclusion can be built coherently in logic. In the second case, we are not actually speaking, there is no well-defined language in which we are encoding the given propositions. With this, I've been able to discern that there are two different activities:
  
  
*
  
*Being able to see something clearly. (Second proof)
  
*Being able to speak something in a language, and if we can speak it, then we assume it is true. (First proof)
  
  
  Is this what induction is about? 

 A: For your "side question": You're missing something absolutely essential about induction - the base case. In a proof by induction, one must show not only that $P(n) \Rightarrow P(n+1)$, but also that $P(1)$ holds (or $P(0)$, or $P(2)$, or wherever you want $P$ to start being true). The standard analogy is of a sequence of dominoes; by showing $P(n) \Rightarrow P(n + 1)$, we've shown that each domino is heavy enough to knock the next one down, but we don't know that any of them fall at all until we've shown that the first one does. We could use some random other formula in the induction step, sure - for example, we could do the following attempted induction:
Suppose that $1 + 2 + 3 + \cdots + n = 1 + \frac{n(n+1)}{2}$. Adding $n + 1$ to both sides and simplifying, we obtain $1 + 2 + 3 + \cdots + n + (n + 1) = 1 + \frac{(n+1)(n+2)}{2}$, which seems to complete the induction. The problem is that the missing step doesn't work - $A_1$, which in this case is the statement $1 = 1 + \frac{1(1+1)}{2}$, is false. Analogously, the first domino does not fall.
To respond to your main question: The second proof is not really a proof. You've successfully demonstrated that the claim is true when $n = 3$, and you've given a good reason to believe that it will be true for other values of $n$; but that's not "proof". How do we know that there's not some very large $n$ with just the right properties so that the "teeth" of your triangles don't quite line up right? The proof by induction, however, is a proof, because all that's required in order to be sure that no $n$ escapes it is the axiom "all natural numbers are reachable by induction".
The key difference is that the second "proof" hinges heavily on intuition; that's why it "feels" more natural to you, but that's also why it isn't proof - intuitions can be wrong, sometimes very badly wrong. The first proof uses only logic, which is as unarguable as we can reasonably expect to achieve.
As for the speak/see distinction, I sort of see (forgive the pun) what you're getting at, but it's not quite right. Just because we can "say" something clearly doesn't mean we assume it's true - there are plenty of obviously false things we can say clearly, like "$1+1=3$". But it is the case that we (or rather, mathematicians in general) do not consider something proven unless we can "speak" the proof clearly and correctly.
