Question

Consider the recursive algorithm given to compute factorial. Which statement below most closely relates to the concept of the inductive hypothesis in induction?

		n = 0
		factorial(n-1)
		return n * factorial(n-1)
		return

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

You are a pop star performing a concert for your fans. You say “Everybody put your hands up!” and you count 28 hands. Assuming everyone in your audience has 2 hands, how many audience members are there?

		Product rule
		Sum rule
		Subtraction rule
		Division rule

Answer 1

i)according to the recursive function of the factorial of a number,

return n*factorial(n-1) closely relates to the inductive hypothesis.

factorial(3)

=3*factorial(2)

=3*2*factorial(1)

=3*2*1*factorial(0)

=6

suppose for some k,factorial(k)=k*factorial(k-1)=k!

factorial(k+1)=(k+1)*factorial(k+1-1)[by inductive hypotheses]

=(k+1)*k*factorial(k-1)

=(k+1)*k*(k-1)*factorial(k-2)

.

.

.

=(k+1)!

ii)

this problem will be solved by the division rule as the number in the audience will be defined as total number of hands divided by 2,

ie,

audience head count=28/2=14