Question

DISCRETE STRUCTURE

Which of the following would not be a possible return value for the base case of a recursive algorithm to compute the sum of the first n odd numbers?

		1
		n (n + 1)
		2n - 1
		n2

Which counting rule is best suited to solving the following problem:

Imagine you are surveying a group of travellers. 45 have visited Spain, 39 have visited France, and 12 have visited Spain and France. How many travellers have been to Spain or France (or both)?

		Product rule
		Sum rule
		Subtraction rule
		Division rule

Answer 1

Solution:

1)

The answer is n(n+1)

Explanation:

For any value of n, see that the value n(n+1) is even.

So this cannot be a return value for a algorithm that computes the sum of n odd numbers.

2)

The answer is Subtraction rule.

The subtraction rule is used in the following scenarios.

When a task can be done in n1 ways and another task can be done in n2 ways, then the total number of ways to do either of the task or both can be found using the subtraction rule.

Here, the number of travellers that have been to france or spain or both can be found using the subtraction rule.