3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – user123
    Sep 23 '18 at 16:43
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.