Let's say we have an arithmetic progression: $a_{n+1} = a_n + k$. Fair enough, now I want to prove $a_{n+m} = a_n + mk$. This is how I do it:
$$a_{n+2} = a_{(n+1)+1} = a_{n+1} + k = a_n + k + k = a_n + 2k$$ $$a_{n+2} = a_n + 2k$$
Oh well, now I replace $2$ with $m$ and here it's proved. The replacement part doesn't seem to be strongly mathematical and is based rather on intuition. Even if the end result is correct, the usage of intuition (or common sense, or whatever you call it) doesn't feel like a legit way to prove things.
Please tell me if I am wrong and can you think of any strongly algebraic ways to prove this exact example? Thank you
Replacing $2$ with $m$ as you did in the question is not justified, since the fact a statement is true for $2$ does not necessarily imply it is true for any other arbitrary integer $m$.
The common way to prove these kind of statements is by induction (see below).
However, as long as you are willing to give up some rigorousness, you can write: $$ a_{n+m} = a_{n+m-1} + k = a_{n+m-2} + 2k = \cdots = a_{n} + mk $$ The above sequence of equations is intuitively similar to what you did, but is more justified, as it shows the actual steps taken to get from $a_{n+m}$ to $a_{n} +mk$. To see why, note that once we fix $m$, we have a finite number of steps, so the ellipsis ($"\cdots"$) could be replaced by an actual sequence of $m$ equations. This it will probably be considered legit in most circumstances.
Proof by induction
Base case ($m = 0$): The statement is trivially true when $m=0$, since $\,a_{n+0} = a_{n}= a_{n} + 0k$.
Inductive step: Assuming the statement is correct for $m$, we note that: $$ a_{n+(m+1)} = a_{(n+m)+1} = a_{n+m} + k= (a_{n} + mk) + k = a_{n} + (m+1)k $$ This means that if we assume the statement is correct for $m$, then it must also be correct for $m+1$. This completes the proof.