2

I am just starting to learn about Mathematical proofs and so far I have learned about Mathematical Induction. I would like to know in its core, what is the main conceptual difference between proving something using Induction and Deduction.

Example to illustrate my question:

Let's say I wanna prove that the following statement is true:

1 + 3 + 5 + ... + (2n-1) = n²

Using Induction:

We prove for the base, thus, when n = 1

Left = 1 | Right = 1² = 1

Therefore it works for my base case

Now, by assumption: n = k where k is a natural number

Then: 1 + 2 + 3 +...+ (2k-1) = k²

If it is true, it should work for n = k + 1, thus: 1 + 2 + 3 +...+ (2k-1) + (2k + 1) = k² + (2k + 1)

k² + (2k + 1) can be factroized as (k + 1)²

So we've just prove that the sentence works for n = k + 1, therefore, it works for any natural number.

Now let's prove by deduction:

We can easily recognize the series {a} = 1 + 2 + 3 + ... + (2n-1) as the sum of odd numbers and it is an Arithmetic Progression in its core, being the (2n-1) the General Term. We know that the general form for summing up an Arithmetic Progression is: S = (n/2) × [2a + (n−1)d]

In this case a is equals to 1 and d is equals to 2 Replacing in the formula, we get: (n/2) × (2n) which is n²

Then we found out by Algebra that the statement is true

So, What is the difference between using the two methods?

Thanks in advance

Matheus Minguini
  • 159
  • 2
    I think the example you used is not particularly good, since the "general form" formula you used in the argument "by deduction" is established inductively. – Andrés E. Caicedo Nov 21 '19 at 17:40
  • Despite the name, mathematical induction is a kind of deduction. – Noah Schweber Nov 21 '19 at 22:39
  • If you try googling deduction v induction, you'll largely get discussions where the latter term is defined differently, so I'm not surprised you asked about it here. – J.G. Nov 21 '19 at 22:41

1 Answers1

1

Well it can be said that deduction is using given data and some acquired knowledge or rules to prove that a certain property is true, so it is arriving to a result by logical reasoning.

Induction ofcourse also uses logical reasoning, but it is used when you want to prove that a certain property is true for any natural number $n$. Also even if you want to prove that a property is true for any $n$, the method of induction differs than that of deduction as in your example. Induction proves that a property is true for $n=1$ first(or $n=0$ or ... according to the property you're proving), assumes its true up to order $n$, and then proves that it is true for $n+1$, by doing that you will have proved that your property is true for any $n$. Deduction, on the other hand, directly proves the property for any $n$ using some rules.

Fareed Abi Farraj
  • 3,446
  • 2
    The claim about $\sqrt 2$ is not true. Many proofs of irrationality use induction at their core. For instance, the fact that any fraction is equivalent to one in reduced terms is essentially inductive. – Andrés E. Caicedo Nov 21 '19 at 17:42
  • Thank you ! Never seen such thing before and just checked it out, it is a nice one... – Fareed Abi Farraj Nov 21 '19 at 22:34
  • 2
    @AndrésE.Caicedo In fact any proof has to use induction - it's consistent with Robinson arithmetic that $\sqrt{2}$ is rational. – Noah Schweber Nov 21 '19 at 22:38