Natural Numbers: Proving Statements w/ Induction

[littleHilbert]

Hello!

Question:

if it is asked to prove a statement A(n_1,...,n_k) for all natural numbers n_1,...,n_k, is it actually enough to check its truth by induction on just one of the counters, say n_1?

 

[Mark44]

I'm not sure you are saying what you mean. If you are asked to prove a statement A(n) for all natural numbers 1, 2, 3, ..., then yes, induction is the way to go.

Or is your statement a function of k different natural numbers? Can you give a simple example of a statement you're talking about?

 

[Tac-Tics]

With one-variable induction, you can think of the induction as walking up a ladder. Draw each sentence in a (one-dimension) grid.

A(0)
A(1)
A(2)
A(3)
...

Usually, in induction, you have to prove two things:
* A(0) is true.
* If any sentence in the grid is true, the one beneath it is also true. (A(n) => A(n+1))

Once you have proven these two things, you can start at A(0) and "walk" up the ladder, proving each is true. More importantly, given any A(n), you can use those to rules to show that A(n) is true.For induction on more variables, things are slightly more complicated. Start with induction on two variables: A(x, y).

Draw these sentences out in a (two dimensional) grid:

A(0, 0) A(1, 0) A(2, 0) ...
A(0, 1) A(1, 1) A(2, 1) ...
A(0, 2) A(1, 2) A(2, 2) ...
A(0, 3) A(1, 3) A(2, 3) ...
...       ...        ...       ...

Now, you're not simply walking down a line. You have to fill an area. There are a few different ways to do it. For example, you might prove A(x, y) is true for all x and y by:
* Proving A(0, 0) is true
* Proving that for any element in the grid, the one below it is true. (A(n, m) => A(n+1, m))
* Proving that for any element in the grid, the one to the right of it is true. (A(n, m) => A(n, m+1))

If you have all three of those proven, then you can again start at A(0, 0) and walk left and down until you reach any arbitrary statement you want to verify.

You can also it it other ways though. You can break it into two singular inductions:
* Prove A(0, 0).
* Prove that if any sentence is true, all the ones below it are also true via single-variable induction.
* Prove that if any sentence is true, all the ones to the right are also true, via single-variable induction.

You can also do more exotic things if the problem calls for it. But the idea is the same. As long as you can reach any statement in the grid by taking a finite number of induction steps, you have proved the whole grid contains nothing but truths.

This extends easily to any finite number of variables. For A(n_1, ..., n_k), you simply use a k-dimensional grid.

 

[littleHilbert]

I'm not sure you are saying what you mean. If you are asked to prove a statement A(n) for all natural numbers 1, 2, 3, ..., then yes, induction is the way to go.

Or is your statement a function of k different natural numbers? Can you give a simple example of a statement you're talking about?

An example is

\binom{n+m}{k}=\displaystyle\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}. It is asked to prove it for all naturals n,m,k.

They say it is enough to prove it for example just for m. The reason, which was brought forward, is that in the induction step we assume the truth of the identity for fixed m and for all n and k. I was not sure we could use it as the induction hypothesis straightaway. As Tac-Tics points out the whole proof should have a staircase structure once we start the induction on one of the counters. This is my opinion too.

At the same time it is reasonable to assume that the induction hypothesis A(m) (here m is arbitrary but fixed) is logically equivalent to A(n,k) (here it holds for all n and k), which in this case makes one think that it's not required to check the truth of A(n,k) by induction on n and k. But is it really an equivalence in a general setting?