0

If I want to do a mathematical double induction on $n$ and $t$ where $n \in \mathbb{N}$ and $1 \leqslant t \leqslant n$ then obviously the base step is $P(n=1,t=1)$ but how do I implement the induction hypothesis. Im very confused as I can’t assume $P(n,t+1)$ to be true nor $P(n+1, t)$ to be true either as I don’t know whether $t+1>n$ or not.

What statements should I then assume and which statement should I prove in the inductive step?

Partey5
  • 1,280

2 Answers2

1

This is going to depend a lot on exactly what you're trying to prove, but here is a general idea for an inductive approach:

Let $Q(n)$ be the statement "$P(n,t)$ for all $t$ between $1$ and $n$", and prove that $Q$ is satisfied for all natural numbers using induction. In each inductive step, you can again use induction: prove $P(n,t+1)$ from assuming both $Q(n-1)$ and $P(n,t)$.

Arthur
  • 199,419
  • My question is: Show that if a set of $n$ boys satisfies Hall’s marriage condition and each individual boy knows at least $t>n$ girls then the number of possible marriage arrangements between boys and girls is greater than or equal to $t!/(t-n)!$ or if each individual boy knows at least $t\leqslant n$ girls then the number of possible marriage arrangements is greater than or equal to $t!$ – Partey5 Feb 20 '20 at 12:47
  • @Anteater23 I suggest you make a new question post with the particular problem baked in. That way you can get answer posts tailored to what you are actually asking about, rather than a long comment thread going back and forth between me and you, which no one else is going to ever see. – Arthur Feb 20 '20 at 13:00
  • I have posted the question in another thread with a bounty. But no one has provided an answer as of yet except one person who linked something in which double induction was used. – Partey5 Feb 20 '20 at 14:48
1

There are different solutions possible, depending on your exact problem.

  • The first one, which probably works, but is not elegant at all is to prove by induction on $n$ the property $\forall 1\leq t\leq n, P(n,t)$. You would prove the base step by setting $n=1$ which forces $t=1$, and for the induction case, you suppose the property for $n$, and prove by induction on $t$ that for all $1\leq t\leq n+1$, you have $P(n+1,t)$. Note that you have to adapt this method to your case, so that you can reduce your problem to a subproblem in the induction step.

  • The second solution I can think of, which might not be applicable, but is worth trying, is to try and reduce it to a single induction. For that you can try and find a combination of $n$ and $t$ (say $n+t$ for instance) such that $P(n,t)$ with $n+t = k$ implies $P(n',t')$ with $n'+t' = k+1$, and you can then perform the induction on $k$.

These are very generic, and without any more precisions, I can't give you a more specific answer

Thibaut Benjamin
  • 1,272
  • The induction I’m trying to show is Marshall Halls Theorem on pg 4 of this link https://www.math.tamu.edu/~catherine.yan/Files/C2A.pdf – Partey5 Feb 20 '20 at 12:42
  • I’m new to this and the induction isn’t set out very clearly for someone of my level. – Partey5 Feb 20 '20 at 12:43
  • Show that if a set of $n$ boys satisfies Hall’s marriage condition and each individual boy knows at least $t>n$ girls then the number of possible marriage arrangements between boys and girls is greater than or equal to $t!/(t-n)!$ or if each individual boy knows at least $t\leqslant n$ girls then the number of possible marriage arrangements is greater than or equal to $t!$ – Partey5 Feb 20 '20 at 12:46
  • I have to admit that the structure of the induction is very badly highlighted in this document, as is often the case in computer science, since people are used to much more tricky (structural) inductions than in maths. So I believe the proof here is done following more or less the lines of my first proposal, but skipping a lot of steps - try to write it in the form of my first proposal, and you will see that they are two inductions one inside the other, and the two cases correspond to which induction hypothesis you are using. If you get stuck I can edit to show the structure – Thibaut Benjamin Feb 20 '20 at 12:54
  • Merci. You explained it very well. I will try to have a go using your induction hypothesis. – Partey5 Feb 20 '20 at 12:58
  • Or you could restate it with $m:=n-t+1\ge1$, then use a more typical double induction argument on $m\ge1,,t\ge1$. – J.G. Feb 20 '20 at 13:08
  • That way seems harder to understand for me. – Partey5 Feb 20 '20 at 14:50