Wondering why the induction method of proof is meant to prove something. One thing I find weird is induction proof, I understand how to use it fully and it's not that it is hard, it's just that it doesn't come across as actual "proof".
Let me give you an example:
I was trying to prove the binomial theorem today,
$$
(a+b)^n=
\begin{equation}
\sum_{j=0}^{n} \binom{n}{j}a^{n-j}b^j
\end{equation}
$$
In a nutshell, I spent $30$ minutes trying to find a (satisfactory - at least to me if that makes sense) proof without realizing that the question was asking for an induction proof which when I found out, I easily came to the answer, but that's not the point, the point is that the answer (that I and the book came to) was

For ($a+b)^1$ or $n=1$, the binomial theorem is clear.  No question there.
For $(a+b)^{n+1}$, we get
$$
(a+b)^{n+1}=
\begin{equation}
\sum_{j=0}^{n+1} \binom{n+1}{j}a^{(n+1)-j}b^j    
\end{equation}
$$

My question is, from this proof, how can we still be satisfied that $n=n+1$ clears the theorem? Thank you.
P.S. I am not sure if I made it very obvious, but $\binom{n}{j}$ is a binomial coefficient.

 A: Comments have clarified that the question is how we separate true consequences of induction from false ones. A valid proof needs two ingredients: the base step must be shown to work, and so must the inductive step.
The base step here is $(a+b)^0=\sum_{j=0}^0\binom{0}{j}a^{n-j}b^j$, which simplifies to $1=1$ so is true. With the inductive step, it helps to use slightly different notation: show if the case $n=k$ works so does the case $n=k+1$. In this problem, this looks like$$\begin{align}(a+b)^{k+1}&=(a+b)(a+b)^k\\&=(a+b)\sum_{j=0}^k\binom{k}{j}a^{k-j}b^j\\&=\sum_{j=0}^k\binom{k}{j}a^{k+1-j}b^j+\sum_{j=0}^k\binom{k}{j}a^{k-j}b^{j+1}\\&=\sum_{j=0}^k\binom{k}{j}a^{k+1-j}b^j+\sum_{j=0}^k\binom{k}{j}a^{k+1-(j+1)}b^{j+1}\\&=\sum_{j=0}^k\binom{k}{j}a^{k+1-j}b^j+\sum_{j=1}^{k+1}\binom{k}{j-1}a^{k+1-j}b^j\\&=\sum_{j=0}^{k+1}\binom{k}{j}a^{k+1-j}b^j+\sum_{j=0}^{k+1}\binom{k}{j-1}a^{k+1-j}b^j\\&=\sum_{j=0}^{k+1}\left(\binom{k}{j}+\binom{k}{j-1}\right)a^{k+1-j}b^j\\&=\sum_{j=0}^{k+1}\binom{k+1}{j}a^{k+1-j}b^j,\end{align}$$where the second $=$ assumes the case $n=k$.
A: The "proof" of the inductive step is either incomplete or plain wrong. In the correct proof, we should assume:
$$(a+b)^n=\sum_{j=0}^n{n\choose j}a^{n-j}b^j$$
and prove the same for $n+1$, i.e.
$$(a+b)^{n+1}=\sum_{j=0}^{n+1}{{n+1}\choose j}a^{(n+1)-j}b^j$$
This is normally done this way:
$$\begin{array}{rcl}(a+b)^{n+1}&=&(a+b)^n\cdot (a+b)\\&=&\left(\sum_{j=0}^n{n\choose j}a^{n-j}b^j\right)\cdot(a+b)\quad\text{(here we used the inductive hypothesis)}\\&=&\sum_{j=0}^n{n\choose j}a^{n-j+1}b^j+\sum_{j=0}^n{n\choose j}a^{n-j}b^{j+1}\\&=&a^{n+1}+\sum_{j=1}^{n}{n\choose j}a^{n-j+1}b^j+\sum_{j=0}^{n-1}{n\choose j}a^{n-j}b^{j+1}+b^{n+1}\\&=&a^{n+1}+\sum_{j=1}^{n}{n\choose j}a^{n-j+1}b^j+\sum_{j=1}^n{n\choose {j-1}}a^{n-(j-1)}b^j+b^{n+1}\\&=&a^{n+1}+\sum_{j=1}^{n}\left[{n\choose j}+{n\choose {j-1}}\right]a^{(n+1)-j}b^j+b^{n+1}\\&=&a^{n+1}+\sum_{j=1}^{n}{{n+1}\choose j}a^{(n+1)-j}b^j+b^{n+1}\quad\text{(see Note below)}\\&=&\sum_{j=0}^{n+1}{{n+1}\choose j}a^{(n+1)-j}b^j\end{array}$$
Note: At the critical place, we used the equality ${n\choose{j-1}}+{n\choose j}={{n+1}\choose j}$ known from combinatorics. We also used the fact that ${n\choose 0}={{n+1}\choose 0}={n\choose n}={{n+1}\choose{n+1}}=1$ liberally throughout the proof.

What seems to me to have been done in their solution is: just replace $n$ with $n+1$ and - voila, job done. It does not work as simply as that. Replacing $n$ with $n+1$ just converts your assumption into your (hopefully) conclusion, but you have to connect the two with a sound proof.
A: I suspect that you have misunderstood what is meant by the induction step.  You seem to think that, in this step, you assume the statement in question, which I'll abbreviate as $P(n)$, for all values of $n$ and then prove it fo $n+1$. That would always work, trivially, by just substituting $n+1$ for $n$ in your assumption.  And it wouldn't actually prove anything about $P(n)$.
But that's not what the induction step is.
The actual induction step assumes $P(n)$ for a single natural number $n$ and tries to prove $P(n+1)$.
Sometimes this is stated, confusingly, as "assume $P(n)$ for an arbitrary $n$", and the word "arbitrary" makes it sound as if you're allowed to assume $P(n)$ for all $n$ at once.  That is not the intended meaning of "arbitrary". The intended meaning is that you're not allowed to assume anything about $n$ beyond its being a natural number satisfying $P(n)$.
So the induction step goes like this. Consider one  natural number $n$ about which you assume that $P(n)$ and nothing more. Then try to prove $P(n+1)$.
[To state it more formally, the induction step consists of proving "for all natural numbers $n$, if $P(n)$ then $P(n+1)$."  It does not consist of proving the (trivial but similar-looking) statement "if for all natural numbers $n$ $P(n)$ then $P(n+1)$."  Switching the order of "if" and "for all $n$" makes a huge difference.]
