Explanation Given information: Define a sequence c 1 , c 2 , c 3 , .... , recursively as follows: c 1 = 0 c k = 2 c ⌊ k / 2 ⌋ + k , for all integers k ≥ 2. Proof: PROOF BY STRONG INDUCTION: Let P ( n ) be " c n ≤ n 2 " Basis step: n = 1 c n = c 1 = 0 ≤ 1 = 1 2 = n 2 Thus P (1) is true. INDUCTIVE STEP: Let P ( 1 ) , P ( 2 ) , ... , P ( k ) be true, thus c i = ≤ i 2 for i = 1 , 2 , ... , k and let k ≥ 2. 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. c k + 1 = 2 c ⌊ ( k + 1 ) / 2 ⌋ + k c k = 2 c ⌊ k / 2 ⌋ + k = 2 c ( k + 1 ) / 2 + 2 ( k + 1 ) / 2 is an integer ≤ 2 ⋅ ( ( k + 1 ) / 2 ) 2 + 2 P ( ( k + 1 ) / 2 ) is true = 2 ⋅ ( k + 1 ) 2 4 + 2 = k 2 + 2 k + 1 2 + 2 ( a + b ) 2 = a 2 + 2 a b + b 2 = k 2 2 + k + 3 2 ≤ k 2 2 + k 2 2 + 3 2 2 k ≤ k 2 when k ≥ 2 = k 2 + 3 2 ≤ k 2 + 2 &

5th Edition

ISBN: 9781337694193

Author: EPP, Susanna S.

Publisher: Cengage Learning,

See similar textbooks

Concept explainers

Sequence and Series

A sequence is defined as a collection of things. Series is defined to sum the things one by one in the sequence. It was invented by German mathematician Carl Friedrich Gauss.

Videos

Question

Chapter 11.4, Problem 23ES

To determine

To prove:

Show that cn≤n2 for all integers n≥1.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 11.4, Problem 22ES

Chapter 11.4, Problem 24ES

Students have asked these similar questions

In the figure below, m₁ || m² and ms ms. 42° m₁ A m3 m4 to What is the value of x? 'ms •m₂ ○ A. 42 ○ B. 48 ○ C. 138 ○ D. 158

Three streams - Stream A, Stream B, and Stream C - flow into a lake. The flow rates of these streams are not yet known and thus to be found. The combined water inflow from the streams is 300 m³/h. The rate of Stream A is three times the combined rates of Stream B and Stream C. The rate of Stream B is 50 m³/h less than half of the difference between the rates of Stream A and Stream C. Find the flow rates of the three streams by setting up an equation system Ax = b and solving it for x. Provide the values of A and b. Assuming that you get to an upper-triangular matrix U using an elimination matrix E such that U = E A, provide also the components of E.

A 315-N force F and 70-N-m couple M are applied to co rner A of the block shown. Replace the given force -couple system with an equivalent force -couple systemat corner D

Chapter 11 Solutions

Discrete Mathematics With Applications

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.