Reference no: EM132250208
Mathematical Expression and Reasoning for Computer Science Assignment -
Question 1 - Induction and sequences
Consider the following definition of a sequence of numbers:
![1975_figure.png](https://secure.expertsmind.com/CMSImages/1975_figure.png)
For example, d0 = 1, d1 = 1, d2 = 2, d3 = 3/2, and d4 = 8/3. Our goal is to prove the following statement: "For all natural numbers n, dn > √n if and only if n is even."
Complete the following two proofs, which together will prove the above statement.
(a) Prove the following using induction: ∀n ∈ Z+, d2n-1 ≤ √(2n - 1).
Hints: in the induction step, write d2k+1 in terms of d2k-1 using the given definition of the sequence. Later as an intermediate step, use difference of squares: (2k - 1)(2k + 1) = 4k2 - 1.
(b) Prove the following (with or without using induction): ∀n ∈ N, d2n > √(2n).
You may use the statement you proved in part (a) in this part.
Question 2 - Number Representations
As you might suspect, it is possible to represent numbers in other ways besides decimal (base-10) and binary (base-2). One intriguing representation is balanced ternary.
In balanced ternary, numbers are represented as sequences of digits (dk-1dk-2 · · · d1d0)bt, where each digit di is T, 0, or 1, with "T" used to represent the value -1. The value of sequence (dk-1dk-2 · · · d1d0)bt is then simply i=0Σk-1di × 3i.
For example, (T01)bt represents the number (-1) × 32 + 0 × 31 + 1 × 30 = -9 + 1 = -8.
(a) (i) Write the decimal value of the balanced ternary number (T011T)bt.
(ii) Write the balanced ternary representation of the decimal number 210 that doesn't have any leading zeroes.
(b) Prove using induction that ∀n ∈ Z+, 6|3n - 3.
(c) Let x ∈ N and n ∈ Z+. We say that x is n-digit positively balanced if and only if it has a balanced ternary representation (dn-1dn-2 · · · d1d0)bt in which none of the digits are equal to T. For example, the decimal number 31 is 4-digit positively balanced, with the representation (1011)bt, and it also is 6-digit positively balanced, with the representation (001011)bt.
Prove, by induction, the following statement:
∀n ∈ Z+, ∀x ∈ N, (x is n-digit positively balanced) ⇒ 6 | x - 2 ∧ 6 | x - 5
You may use part (b) and the Quotient-Remainder Theorem (QRT) in this question.
Question 3 - Properties of Asymptotic Notation
Prove or disprove each of the following statements.
You may use the "max", ceiling, and floor functions in your solutions. However, you may not use any external facts of Big-Oh/Omega/Theta, and instead should only be using their definitions in your proofs.
The following definitions apply to part (d).
Definition 1 (non-decreasing). Let f : N → R≥0. We say that f is non-decreasing if and only if for all x, y ∈ N, if x ≤ y then f(x) ≤ f(y) (note that f(x) and f(y) can be equal).
Definition 2 (power of two). Let n ∈ N. We say that n is a power of two if and only if there exists a k ∈ N such that n = 2k.
Note - Need Only Question 3.
Attachment:- Assignment File.rar