0

Complete beginner on the topic, I can say that I lack the formal way of doing this. What I am trying to understand is: During the "inductive step", instead of using $k + 1$ can we assume $k -1$?, also I would like to know if by proving $k - 1$ we imply that $k + 1$ must also be true. I apologize for not being able to structure the question in a more coherent way.

Paulo Abreu
  • 3
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Sep 29 '22 at 15:07
  • 1
    Do you mean assume $n - 1$ rather than $n$? – N. F. Taussig Sep 29 '22 at 15:09
  • 1
    One could do that but then they would have to start with the $k-1$th term and then go on to proving the $k$th case. Remember that induction is about proving that a certain relation holds AFTER a point, not before it. – Hersh Sep 29 '22 at 15:20
  • If I understood right, during the inductive process, if it holds for $n = k$ it should also hold for the next case $n = k + 1$. I wanted to know if we can do it "backwards". If instead of using the next case we use the previous one being $k - 1$. Maybe my question was too confusing, I might rewrite it. – Paulo Abreu Sep 29 '22 at 15:24
  • Can you perform induction over any inductive set? Yes. Are the positive integers greater than or equal to a particular value of $k$ an inductive set? Yes. Are the integers less than or equal to a particular $k$ an inductive set? Also yes. Is it common to have phrased induction so as to decrease rather than increase? Not at all, but that doesn't make it "wrong" per se, just very nonstandard. Any inductive argument which was phrased as decreasing a value could have been rephrased as an inductive argument which increases a value which happens to be subtracted at a later point. – JMoravitz Sep 29 '22 at 15:34
  • Could you have done a "backwards induction" here for this particular summation? I suppose that depends on what you wanted to prove... but it sounds messy and sounds like it wouldn't have proven what you wanted to. It certainly wouldn't have proven the identity holds true for all positive $n$ in any case (which is what most people want to prove)... it would only have proven that the identity holds for all values less than your base case but would have done nothing about proving or disproving that it holds for values larger than your base case. – JMoravitz Sep 29 '22 at 15:36
  • Again, think of a line of dominos which are lined up such that when you knock one over it knocks down all the rest in the same direction. Normally with induction, we have infinitely many domino blocks set up and we push the domino we wish to start with (our base case) in the direction of those dominos which represent the numbers larger than it, causing a chain reaction. We could perfectly well have knocked down the domino to the left rather than to the right if we wanted to... but notice which (if any) dominos that would knock over (and would not knock over). – JMoravitz Sep 29 '22 at 15:39
  • Oh, understood. The way I was thinking probably would create some sort of paradox. Now I understand the reasons behind the base case and why it works. It is not as trivial as it seems. Truly appreciated the explaination, really enlightin. Again, Sorry for not being able to elaborate a better question, maybe at least it was a reflection on how confused I was about the topic haha – Paulo Abreu Sep 29 '22 at 15:53

1 Answers1

0

The argument that you are seeking is do-able, in only a moderately convoluted fashion.

The first thing to do is form the hypothesis $H(n)$ that says that for a specific positive integer $(n)$, that the following formula holds:

$$\sum_{i=1}^n (i) = \frac{n(n+1)}{2}.$$

The next thing to do, which is simply straight algebra, is to prove that if $H(n)$ is false, for a particular positive integer $(n \geq 2)$, then $H(n-1)$ must also be false.

This can be routinely done by calculating (for example)

$$\left[\sum_{i=1}^n (i)\right] - \left[\sum_{i=1}^{(n-1)} (i)\right].$$

So, once it is established that $H(n)$ false implies $H(n-1)$ false, for $n \in \Bbb{Z_{\geq 2}}$, then you are fully justified in deducing that there must be some positive integer $(k)$ such that $k$ is the minimum value so that $H(k)$ is false.

Then, you conclude that the assumption that there exists any positive integer $(n)$ such that $H(n)$ false leads to the inescapable conclusion that $H(1)$ false.

Then, you reason that because $H(1)$ is not false, it is not the case that there can exist any positive integer $(n)$ such that $H(n)$ is false.

Unclear what the source of this problem is. What the above analysis amounts to is using a very powerful Number Theory argument, known as descent, to disprove a hypothesis.

Presumably, if the scenario was presented by a problem composer, then the point is not that this is the most elegant way of demonstrating that $H(n)$ is true for all positive integers $(n)$.

Instead, the point is simply to introduce the Math student to the descent weapon, which will be the most elegant weapon to use in other Number Theory problems.

user2661923
  • 35,619
  • 3
  • 17
  • 39