4

Function $f(t,n,m)$ is defined for $0\le t \le T$, $n\in\{0,\ldots\}$ and $m\in\{2,\ldots\}$.

We would like to show some properties are true for any $t$ and all $n$ and $m$.

I thought perhaps I can show this by induction. So I started by the base case of $f(t, 0, 2)$ and it turned out we can show such properties hold for $f(t,n,2)$, $n\in\{0,\ldots\}$.

But to generalize our results for $f(t,n,m)$, we need to have some properties to be true for $f(t,n + 1,m - 1)$.

So I'm confused as to how the induction assumption should be here.

  • Since you can still "descend" in the $m$, you should probably do an induction over $m$ of the form $P(m)$: "$\forall n, \forall t,$ [something]" I think. – Bruno B Nov 12 '22 at 13:52
  • 1
    Thanks for the comment. That's what I thought initially. So does that mean the steps are: 1) Showing results are true for $f(t,n,2)$, for $n\in{0,\ldots}$. 2) Assuming properties are true for $f(t,n,m-1)$, for $n\in{0,\ldots}$ and $m\in{3,\ldots}$. 3) Showing results are true for $f(t,n,m)$, for $n\in{0,\ldots}$ and $m\in{3,\ldots}$? –  Nov 12 '22 at 13:57
  • Yeah that should work. – Bruno B Nov 12 '22 at 13:59

1 Answers1

3

Any reason why you want to descend on the $m$, given that you need to prove the result for $m$ being $2$ and up?

Anyway, all you need to do is to have some scheme that will make 'all the dominoes fall over'. For 2 variables, there are many such schemes, but the simplest is probably to start with base case $f(t,0,2)$, and then show the following two things:

  1. For any $n\geq 0$ and $m \geq 2$: if $f(t,n,m)$, then $f(t,n+1,m)$

  2. For any $n\geq 0$ and $m \geq 2$: if $f(t,n,m)$, then $f(t,n,m+1)$

Notice that in effect something like $f(t,1,3)$ is now shown in two different ways: because we have $f(t,0,2)$, we have by 1 that $f(t,1,2)$, and thus by 2 that $(t,1,3)$. But you can also say that we have $f(t,0,2)$, and thus by 2 you have $f(t,0,3)$, and thus by 1 you have $f(t,1,3)$.

In other words, this method seems like it's overkill. Is that bad? Shouldn't you find some scheme that gets to every point through one and only one path? No, there is no need for that at all: you just want to make all the dominoes fall over, and this scheme works just fine .... unless of course the intricacies of what you need to prove naturally suggest a different scheme.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • 2
    Thanks for the answer. I don't need to descend on $m$ but based on the structure of the function, to show $f(t,n,m)$ is true, we need some properties to be true. Those properties are in $f(t,n+1,m-1)$. So I thought maybe the assumption should be on $(n+1,m-1)$. Does that make sense? –  Nov 12 '22 at 14:04
  • 1
    So you are saying that you can show $f(t,n,m)$ if you have $f(t,n+1,m-1)$? OK, so then for the induction you do want to ascend on $m$: e.g. it sounds like that given that $f(t,2,4)$, you can now easily show that $f(t,1,5)$ .. or in general, that if you have $f(t,n+1,m-1)$, you can get $f(t,n,m)$, which is to say that if you have $f(t,n,m)$, then you also know $f(t,n-1,m+1)$ (with edges cases carefully indicated). OK, so then yes, you can move through the whole 2D grid by first covering the whole $f(t,n,2)$ row and then do the rest of the grid by going from $f(t,n,m)$ to $f(t,n-1,m+2)$. – Bram28 Nov 12 '22 at 14:15
  • I just realized 1. in the answer is trivial for our function! Does that mean the three steps in the answer are equivalent to these three? 1) Prove results are true for $f(t,n,2)$, for $n\in{0,…}$. 2) Assume properties are true for $f(t,n,m−1)$, for $n\in{0,…}$ and $m\in{3,…}$. 3) Prove results are true for $f(t,n,m)$, for $n\in{0,…}$ and $n\in{3,…}$? –  Nov 12 '22 at 15:17
  • @VultraUiolet 2) and 3) are part of the same one inductive step. And yes, that would be the same as the 2. in my answer – Bram28 Nov 12 '22 at 21:08