[SOLVED] Homework 3 cs 417

Problem 1. Use Gauss’s method to show that
1 + 3 + 5 + . . . + (2n − 1) = n
2
.
For example
1 + 3 = 4 = 22
, 1 + 3 + 5 = 9 = 32
.
Problem 2. (10 points) Do 5 questions in Section 3.10 (Discussion questions).
For the remaining problems, please submit a python file (jupyter notebook is also fine).
For questions that ask for an explanation, please provide your answers as comments.
Problem 3. (10 points) Do Questions 4 and 5 in Section 3.11 (Programming Exercises).
Problem 4. A triangular number is a number that can be arranged in the shape of an
equilateral triangle. Mathematically, n is a triangular number if we can find a positive
integer k such that
n =
k(k + 1)
2
.
The first few triangular numbers are described in the picture below.
Write a function to check whether a given number n is triangualr or not. What is the
big O-performance of your program?
Problem 5. Let am be a sequence given by the following recursive formula
a0 = 2, a1 = 5, am = 5am−1 − 6am−2 for m ≥ 2.
The following questions are considered to be independent from each other (though, if you
want to use one to solve the others, that is fine).
1
(1) Write a function to calculate the kth term of this sequence. You function should
take k as the argument and return ak.
(2) Given a number n. Write a function to check whether n belongs to this sequence
(namely, there exists k such that ak = n). For example, 13 belongs to this sequence
because a2 = 13. On the other hand, 20 is not a member of this sequence. Use
a count variable inside your function to estimate the number of assignments in
your function for n = 102
, 103
, 104
, 105
, 106
, 107
. What do you think is the big Operformance of your algorithm?
(3) What if I tell you that the general formula for am is am = 2m + 3m.