<s>[INST] Trapped in Induction, how to get out? Example 1:
Prove by induction that $1+3+5+...+(2n-1)=n^2 \text{ for all } n \in \mathbb{N}....(*)$
Proof:
Step 1: For $n=1$, left-side we have $(2(1)-1) = 1$. Right-side we have $(1)^2 = 1$.
Step 2: Suppose (*) is true for some $n=k \in \mathbb{N}$ that is 
$$1+3+5+...+(2k-1)=k^2$$
Step 3: Prove that (*) holds true for $n=k \in \mathbb{N}$ that is (adding $(2k+1)$ to both sides)
$$1+3+5+...+(2k-1)+(2k+1)=(k)^2+(2k+1)$$
we have 

which shows both sides are equal?
but you can do this to several number of problems....
Example 2:
Prove by induction that $1^3+2^3+...+n^3=(1+2+...+n)^2 \text{ for all } n \in \mathbb{N}....(*)$
Proof:
Step 1: For $n=1$, left-side we have $1^3 = 1$. Right-side we have $(1)^2 = 1$. Which shows both sides are true.
Step 2: Suppose (*) is true for some $n=k \in \mathbb{N}$ that is 
$$1^3+2^3+...+k^3=(1+2+...+k)^2$$
Step 3: Prove that (*) holds true for $n=k \in \mathbb{N}$ that is (adding $(k+1)^3$ to both sides)
$$1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k)^2 + (k+1)^3$$
we have 

which shows both sides are equal again...
what am I fundamentally doing wrong?
 [/INST] In Step 3 of the second example, you write "Prove that (*) holds true for $n = k \in N$", but that should be $n = k + 1$. 
I find it useful in proofs like this to write down something I call $P(n)$, the proposition that I want to prove, which is typically meant to be true for every integer $n$. In your example 3, $P(n)$ is the statement
$$
1^3+2^3+...+n^3=(1+2+...+n)^2 
$$
That means that $P(1)$ is the statement
$$
1^3=(1)^2 
$$
and $P(2)$ is the statement
$$
1^3 + 2^3=(1+2)^2 
$$
and so on. 
Now you can say this:
I'm going to assume that for some $k \in \mathbb N$, $P(k)$ is true, i.e., that 
$$
1^3+2^3+...+k^3=(1+2+...+k)^2 
$$
And using only algebraic manipulation, I'll use this to establish that $P(k+1)$ is true, i.e., that 
$$
1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k + (k+1))^2. 
$$
Now you have a starting point and a clear goal. 
I'd say, at this point:
From the hypothesis, we have 
$$
1^3+2^3+...+k^3=(1+2+...+k)^2 
$$
Adding $(k+1)^3$ to each side, we get
$$
1^3+2^3+...+k^3+ (k+1)^3=(1+2+...+k)^2 + (k+1)^3 
$$
To finish the proof, we have to show that the right hand side is the same as $(1 + 2 + \ldots + (k+1))^2$. To do so, let's look at the difference between these two, 
\begin{align}
S &= (1+2+...+k)^2 + (k+1)^3  - ((1+2+...+k+(k+1))^2) 
\end{align}
If we can show $S = 0$, we're done. Well, 
\begin{align}
S 
&= (1+2+...+k)^2 + (k+1)^3  - ((1+2+...+k+(k+1))^2)\\
&= (1+2+...+k)^2 - (1+2+...+k+(k+1))^2 + (k+1)^3  
\end{align}
The first two terms look like $A^2 - B^2 = (A-B)(A+B)$, so
\begin{align}
S 
&= (1 + 2 + \ldots + k)^2 - (1 + 2 + \ldots + k+(k+1))^2 + (k+1)^3  \\
&= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k+(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3  \\
&= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k +(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3  \\
&= -(k+1)\cdot(2 (1 + 2 + \ldots + k) + (k+1)) + (k+1)^3  \\
&= -(k+1)\cdot(2 \frac{k(k+1)}{2} + (k+1)) + (k+1)^3  \\
&= -(k+1)\cdot( k(k+1) + (k+1)) + (k+1)^3  \\
&= -(k+1)\cdot( k(k+1) + 1\cdot(k+1)) + (k+1)^3  \\
&= -(k+1)\cdot( (k+1)(k+1) ) + (k+1)^3  \\
&= -(k+1)^3 + (k+1)^3  \\
&= 0. 
\end{align}
</s>