Proof: Proceed by induction

Base case $P(t=1)=n_1$, which is even since $n$ is an even integer. True. Assume $P(t)$, i.e. if $n_1,n_2,\cdots n_t$ are even, then $n_1+n_2+...+n_t$ is even, is true.

Inductive step: $P(t+1)=n_1+n_2+...n_t+n_{t+1}$. Since $n_1+n_2+...+n_t$ is assumed to be even and $n_{t+1}$ is even, an even $+$ even gives an even number. Therefore $P(t+1)$ is shown to be true by induction.

Please let me know if this proof is satisfactory as I am relatively new to induction proofs.

  • 2
    $\begingroup$ Satisfactory, but your MathJax isn't. $\endgroup$ – Parcly Taxel Feb 28 '18 at 3:59
  • $\begingroup$ For reference: Mathjax tutorial $\endgroup$ – JMoravitz Feb 28 '18 at 4:10
  • $\begingroup$ Don't you need to prove that the sum of $t$ terms that are even is itself even rather than just asserting it to be true? $\endgroup$ – Michael McGovern Feb 28 '18 at 4:18
  • $\begingroup$ @MichaelMcGovern: No, that's the induction hypothesis. $\endgroup$ – Eric Wofsey Feb 28 '18 at 4:23

You have the right idea, but some of your notation and phrasing is off.

First, note that a statement like "$P(t=1)=n_1$" doesn't make sense, for several reasons. First, you've never defined what $P(t)$ means. Second, even if you had defined it, $P(t=1)$ would not make sense; instead you would just write $P(1)$. Third, the usual thing to call "$P(t)$" here would be the statement that if $n_1,\dots,n_t$ are even integers, then so is their sum. So $P(t)$ (or $P(1)$) is an entire statement, not just a number. It doesn't make sense to say $P(1)=n_1$.

What you can instead say for your base case (after defining what $P(t)$ means) is something like:

To prove $P(1)$, suppose $n_1$ is an even integer. Then the sum we must prove is even is just $n_1$, which we know to be even.

Note how I clearly introduced the variable $n_1$ with "suppose $n_1$ is an even integer" before proceeding to prove anything. This is in general a good practice when proving a "for all" statement: you first start by explicitly mentioning that you are considering a particular instance of the statement.

There are similar issues with your phrasing in the inductive step. Also, the induction hypothesis (where you assume that $P(t)$ is true) should be the start of the inductive step, rather than the end of the base case.

  • $\begingroup$ Does this look better: Assume P(t), i.e. if n1, n2,...,nt are even, then n1+n2+...+nt is even, is true. Then Since n1+n2+...+nt is assumed to be even and nt+1 is even, an even + even gives an even number. Therefore P(t+1) is shown to be true by induction. $\endgroup$ – paul9797 Feb 28 '18 at 4:28
  • $\begingroup$ Yeah, that's a lot better! My main suggestion would be that you explicitly introduce the variables $n_1,\dots,n_{t+1}$ after your first sentence, like I did for the base case. $\endgroup$ – Eric Wofsey Feb 28 '18 at 4:36

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.