The discussion revolves around the use of mathematical induction to prove statements involving multiple natural number variables. Participants explore whether it is sufficient to perform induction on just one variable when proving a statement that depends on multiple variables.
Discussion Character
Exploratory
Technical explanation
Debate/contested
Main Points Raised
One participant questions if proving a statement A(n_1,...,n_k) can be done by induction on just one variable, n_1.
Another participant suggests that induction is appropriate for proving statements for all natural numbers, but seeks clarification on whether the statement involves multiple variables.
A participant describes the process of one-variable induction as akin to walking up a ladder, emphasizing the need to prove base cases and the inductive step.
Discussion includes the complexity of induction with two variables, proposing methods to prove statements in a two-dimensional grid.
One participant provides an example involving binomial coefficients, questioning whether proving the statement for a fixed variable m is sufficient to establish the truth for all n and k.
Concerns are raised about the logical equivalence of the induction hypothesis for one variable compared to the multi-variable case, prompting further inquiry into the general applicability of this approach.
Areas of Agreement / Disagreement
Participants express differing views on the sufficiency of using induction on a single variable for multi-variable statements. The discussion remains unresolved, with no consensus on whether this approach is universally valid.
Contextual Notes
Participants highlight the need for clarity on the assumptions involved in using induction for multiple variables and the potential limitations of applying single-variable induction to multi-variable cases.
#1
littleHilbert
55
0
Hello!
Question:
if it is asked to prove a statement [tex]A(n_1,...,n_k)[/tex] for all natural numbers [tex]n_1,...,n_k[/tex], is it actually enough to check its truth by induction on just one of the counters, say [tex]n_1[/tex]?
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?
#3
Tac-Tics
816
7
With one-variable induction, you can think of the induction as walking up a ladder. Draw each sentence in a (one-dimension) grid.
Code:
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:
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.
#4
littleHilbert
55
0
Mark44 said:
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
[tex]\binom{n+m}{k}=\displaystyle\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}[/tex]. 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?