# Logic Question - Double Induction

I'm confused with the logic of a problem. I'm trying to prove a statement of the form $$P(n,k)$$ where $$1 \leq k\leq n$$. Based on the problem it seems natural to use (strong) induction on $$n$$. Proving the base case is easy, and then when you want to prove $$P(n,k) \implies P(n+1,k)$$ you need to use $$P(n-1,k)$$ and $$P(n-1,k-1)$$, so I though that I needed to do something like double induction on $$n$$ and $$k$$. But these wouldn't really work because $$k$$ is bounded by $$n$$. Is there a way that I get get around this?

I hope to get some help only with just this information. I really don't want to post the problem because it is a homework problem and I don't want unnecessary help.

• I just realized how I can fix this, since $k$ depends on $n$ my $P$ statement is really only a statement dependent on $n$. So, I only need induction on $n$. Sep 23 '18 at 16:43

## 1 Answer

It depends on the statement you want to prove.

You can see the statement $$\forall n\in\mathbb N, \forall k\in\{1,\dots,n\},P(n,k)$$ as $$\forall n\in\mathbb N,Q(n)$$ where $$Q(n)=\forall k\in\{1,\dots,n\},P(n,k).$$

Then you show that $$Q(1)$$ is true and that $$\forall n\in\mathbb N,Q(n)\implies Q(n+1)$$ to conclude.

• Yes, I realized this after posting the question! I put it as a comment under my question! Thanks for the help anyways! Sep 23 '18 at 16:47
• Oh xD didn't see it. Answer at the same time lol. It's a pleasure :) Sep 23 '18 at 17:30