Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q31E

Expert-verified

Discrete Mathematics and its Applications

Found in: Page 330

Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later

Short Answer

Prove that 2 divides $n^{2} + n$ whenever n is a positive integer.

2 divides $n^{2} + n$ whenever n is a positive integer

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step: 1

If n=1,

$1^{2} + 1 = 2$

it is true for n=1.

Step: 2

Let P(k) be true.

$k^{2} + k$

We need to prove that P(k+1) is true.

Step: 3

$\begin{aligned} (k + 1)^{2} + (k + 1) \\ = k^{2} + 3 k + 2 \\ = (k^{2} + k) + (2 k + 2) \\ = (k^{2} + k) + 2 (k + 1) \end{aligned}$

It is true for P(k+1) is true.

Most popular questions for Math Textbooks

Prove that if $A_{1}, A_{2}, \dots, A_{n}$ and $B_{1}, B_{2}, \dots, B_{n}$ are sets such that $A j \subseteq Bifor j = 1, 2, \dots, n$ , then $\cup_{j = 1}^{n} A j \subseteq \cup_{j = 1}^{n} B j$

Let P (n) be the statement that $1^{2} + 2^{2} + . . . + n^{2} = n (n + 1) (2 n + 1) / 6$ for the positive integer n .

a) What is the statement P (1) ?

b) Show that P (1) is true, completing the basic step of

the proof.

c) What is the inductive hypothesis?

d) What do you need to prove in the inductive step?

e) Complete the inductive step, identifying where you

use the inductive hypothesis.

f) Explain why these steps show that this formula is true whenever n is a positive integer.

Let $P (n)$ be the statement that a postage of n cents can be formed using 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that $P (n)$ is true for $n \geq 18$ .

(a) Show statements $P (18), P (19), P (20)$ and $P (32)$ are true, completing the basis step of the proof.

(b) What is the inductive hypothesis of the proof?

(c) What do you need to prove in this inductive step?

(d) Complete the inductive step for $k \geq 21$ .

(e) Explain why these steps show that statement is true whenever

Let P(n) be the statement that $1^{3} + 2^{3} + \dots + n^{3} = (n (n + 1) / 2)^{2}$ for the positive integer .

a) What is the statement P(1)?

b) Show that P(1) is true, completing the basis step of

the proof.

c) What is the inductive hypothesis?

d) What do you need to prove in the inductive step?

e) Complete the inductive step, identifying where you

use the inductive hypothesis.

f) Explain why these steps show that this formula is true whenever is a positive integer.

Trace Algorithm 3 when it finds gcd (12,17) . That is, show all the steps used by Algorithm 3 to find gcd (12,17).

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free