Explanation Given information: For each positive integer n, let a n be the number of iterations of the while loop. while ( n > 0) n : = n div 2 end whileCalculation: We know that (from pervious exercise) a n = a ⌊ n / 2 ⌋ + 1 for all integers n ≥ 2 a 1 = 1 Let us determine the first terms of the given recurrence relation: a 1 = 1 = 1 + ⌊ log 2 1 ⌋ a 2 = a ⌊ 2 / 2 ⌋ + 1 = a 1 + 1 = 1 + 1 = 2 = 1 + ⌊ log 2 2 ⌋ a 3 = a ⌊ 3 / 2 ⌋ + 1 = a 1 + 1 = 1 + 1 = 2 = 1 + ⌊ log 2 3 ⌋ a 4 = a ⌊ 4 / 2 ⌋ + 1 = a 2 + 1 = 2 + 1 = 3 = 1 + ⌊ log 2 4 ⌋ a 5 = a ⌊ 5 / 2 ⌋ + 1 = a 2 + 1 = 2 + 1 = 3 = 1 + ⌊ log 2 5 ⌋ a 6 = a ⌊ 6 / 2 ⌋ + 1 = a 3 + 1 = 2 + 1 = 3 = 1 + ⌊ log 2 6 ⌋ a 7 = a ⌊ 7 / 2 ⌋ + 1 = a 3 + 1 = 2 + 1 = 3 = 1 + ⌊ log 2 7 ⌋ a 8 = a ⌊ 8 / 2 ⌋ + 1 = a 4 + 1 = 3 + 1 = 4 = 1 + ⌊ log 2 8 ⌋ a 9 = a ⌊ 9 / 2 ⌋ + 1 = a 4 + 1 = 3 + 1 = 4 = 1 + ⌊ log 2 9 ⌋ ⋯ a 15 = a ⌊ 15 / 2 ⌋ + 1 = a 7 + 1 = 3 + 1 = 4 = 1 + ⌊ log 2 15 ⌋ a 16 = a ⌊ 16 / 2 ⌋ + 1 = a 8 + 1 = 4 + 1 = 5 = 1 + ⌊ log 2 16 ⌋ ⋯ We then note that a n = 1 + ⌊ log 2 n ⌋ appear to be true for these values of n, which we will proof is true. Given: a n = a ⌊ n / 2 ⌋ + 1 for all integers n ≥ 2 a 1 = 1 To proof: a n = 1 + ⌊ log 2 n ⌋ for all integers n ≥ 1 PROOF BY STRONG INDUCTION: Let P ( n ) be " a n = 1 + ⌊ log 2 n ⌋ " Basis step: n = 1 a 1 = 1 = 1 + 0 = 1 + ⌊ log 2 1 ⌋ Thus P (1) is true. INDUCTIVE STEP: let P ( 1 ) , P ( 2 ) , ... , P ( k ) be true, thus a i = 1 + ⌊ log 2 i ⌋ for i = 1 , 2 , ... , k We need to prove that P ( k + 1) is true. FIRST CASE: k odd Since k is odd, k + 1 is even and thus ( k + 1) / 2 is an integer

5th Edition

ISBN: 9780357540244

Author: EPP

Publisher: CENGAGE L

See similar textbooks

Videos

Question

Chapter 11.5, Problem 10ES

To determine

Find an explicit formula for a_n.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 11.5, Problem 9ES

Chapter 11.5, Problem 11ES

Students have asked these similar questions

In a survey, the planning value for the population proportion is p 0.25. How large a sample should be taken to provide a 95% confidence interval with a margin of error of 0.03? Round your answer up to the next whole number. 800 {

Q/ calculate the Fourier series of f(x) on the given interval f(x) = x Sin X 9 -

Q 2/ Calculate the Fourier series of f(x) on the given interval f(x) = x Sin X - 16 x ≤ メ

Chapter 11 Solutions

WEBASSIGN F/EPPS DISCRETE MATHEMATICS

Ch. 11.1 - If f is a real-valued function of a real variable,...Ch. 11.1 - Prob. 2TY Ch. 11.1 - Prob. 3TY Ch. 11.1 - Prob. 4TY Ch. 11.1 - Prob. 5TY Ch. 11.1 - Prob. 6TY Ch. 11.1 - Prob. 1ES Ch. 11.1 - The graph of a function g is shown below. a. Is...Ch. 11.1 - Prob. 3ES Ch. 11.1 - Sketch the graphs of the power functions p3 and p4...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

Find an explicit formula for a n .

Solution Summary: The author explains how to determine the first terms of the given recurrence relation.

Videos

Find an explicit formula for a_n.

Want to see the full answer?

Chapter 11 Solutions

Find an explicit formula for a n .

Solution Summary: The author explains how to determine the first terms of the given recurrence relation.

Videos

Find an explicit formula for an.

Want to see the full answer?

Chapter 11 Solutions

Find an explicit formula for a_n.