• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q18E

Expert-verified Found in: Page 370 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Prove that Algorithm 1 for computing n! when n is a nonnegative integer is correct.

The required algorithm is proved by induction.

See the step by step solution

## Step 1: Base case

The algorithm is for when n is non-negative, the base case is .

factorial (0) = 0!

= 1

## Step 2: Prove that Algorithm 1 for computing n!

By induction hypothesis,

$\begin{array}{r}\mathrm{factorial}\left(\mathrm{k}\right)=\mathrm{k}!\\ \text{factorial}\left(\mathrm{k}+1\right)=\left(\mathrm{k}+1\right)\cdot \text{factorial}\left(\mathrm{k}\right)\\ =\left(\mathrm{k}+1\right)\cdot \mathrm{k}!\\ =\left(\mathrm{k}+1\right)!\end{array}$

Therefore, the required algorithm is proved by induction. ### Want to see more solutions like these? 