Look at following recursive function definition for function $F :\mathbb{N}\times\mathbb{N} \to \mathbb{N}$: $$ \begin{split} F(x,0) & = 0\\ F(x,n) & = x + F(x, n-1) \end{split} $$
Prove by induction over $n$ that $F(1,n) = n$, for all $n \ge 0$.
Studing for my discrete mathematics test. And came over this question, and I dont really know how to solve it.
Did the base case but I dont know how to continue. Tested all kinds of stuff, but I've got stuck in the step case. Came as far as: $$ \begin{split} F(x,n+1)&=x+F(x,n-1+1)\\ &=x+F(x,n)=\\ & = x + x + F(x,n-1)\dots\text{ then I get stuck or dont know if im doing it right.} \end{split} $$ Another example... $$ \begin{split} F(x,n+1)&=x+F(x,n+1-1)...... (n+1)\\ &=F(1,n+1)x+F(x,F(1,n+1-1))=x+F(x,F(1,n))\\ &=x+F(x,n)\dots\text{ then I get stuck again.} \end{split} $$ I don't know if I am doing anything right. Any help would really be appreciated.
Putting $x=1$, we get
$\begin{split} F(1,0) & = 0\\ F(1,n) & = 1 + F(1, n-1) \end{split} $.
If $F(1, n-1) = n-1$ (true for $n=1$), then $F(1,n) = 1 + F(1, n-1) =n $.
In general, as Cesareo pointed out, this same argument can be used to prove that $F(x, n) = nx$.
The two-variable form is just used to confuse. In addition, you don't need strong induction - regular induction is enough.