I think it was Gauss who taught us that $$1+2+...+n = \frac{n(n+1)}2$$ for natural numbers.
We can easily verify this with a proof by induction.
However, what if I would like to find the sum of all the natural numbers between any two given natural numbers (not just between $1$ and a given natural number)? And from there, what if I wanted to generalize to all integers?
Well, using Gauss' reasoning it's not hard to develop an equation that would satisfy this.
For example, I could say that
For all $x$ and all $y$,
The sum between $x$ and $y$ (inclusive: implying that if $x$ and $y$ are equal it will return that value) is:
$$\frac{(x+y)(||x|-|y||)+1)}2$$ where $x,y$ are elements of $\mathbb{Z}$.
I may have typed that in wrong; I'm not sure. But it's not really relevant. What I'm really wondering is how I would go about proving something like this.
My first instinct is that I could just do induction on the process of induction. That is, say we were just sticking with a proof within the natural numbers, if I prove with induction that it is equal to the sum of the values from $1$ to $y$, that is a proof of the base case where $x = 1$. Then I could just do the inductive step on that...proving $2$ to $y$, $3$ to $y$, and so on. And I could do this in such a way that it wouldn't matter whether or not $x>y$ (ie: doing the induction in both directions: doing the induction on the induction with the base case of $1$ to $x$, and doing the induction on the induction with the base case of $1$ to $y$). But there are other ways (more simple ways I think even) that I could go about making sure that it wouldn't matter whether $x>y$.
Nonetheless, my professor says that this method of applying induction on induction will not work. She also says I would have to use function spaces for this proof (which I haven't learned yet). Is my professor correct? Why or why not? Also, are there any other methods for the proof that anyone knows?
http://www.itk.ilstu.edu/faculty/chungli/DIS300/dis300chapter3.pdf
A friend sent me a link to a pretty good paper (3.3) Nested Induction.
http://www.itk.ilstu.edu/faculty/chungli/DIS300/dis300chapter3.pdf