SOLVED EC330  Homework 1

Problem 5).
1. Sums [15 pt]
Provide a closed-form solution to the following problems. Make sure you show the
steps.
a) (
!
!
) !"" !
!!!
b) (
!
!
) ! !
!!!
c) (� ! !
!!! + 5�! − 7� + 10)
2.Exponents and Logs [15 pt]
a) �! ∙ �! ∙ �! ∙∙∙ �!"
b) ���!�!!
c) ���!!(77!! ∙ 77)
3. Combinatorics [10 pt]
a) How many 10-digit hexadecimal numbers do not contain A, B or C?
b) How many integral solutions of x1 + x2 + x3 = 30 satisfy x1 ≥ 2, x2 ≥ 0 and x3 ≥ -3?
4.Induction [20 pt]
a) Proposition: All students love homework equally.
Proof:
• Base Case. For n = 1, a single student clearly loves homework exactly as
much as him- or herself, so the base case holds.
• Inductive Hypothesis. Assume any k students love homework equally.
• Inductive Step. Consider k + 1 students.
i. By the inductive hypothesis, the first k students all love homework
equally.
ii. By the inductive hypothesis, the last k students all love homework
equally.
iii. Therefore, all k + 1 students love homework equally, and the
proposition holds by the principle of induction. 
2
Clearly, not all students love homework equally. Which of the following is true?
Briefly explain your choice. [5 pt]
1) The proof of the base case is incorrect.
2) The inductive hypothesis does not hold.
3) The application of the inductive hypothesis in step i is incorrect.
4) The application of the inductive hypothesis in step ii is incorrect.
5) The inductive step logic in step iii is flawed for at least one value of k.
b) Proposition: Consider the function � defined as follows.
�(�) = � � = 1, 2, 3
� � = � � − 1 + � � − 2 + � � − 3 � ∈ ℕ and � > 3
Show that ∀� ∈ ℕ, � � < 2!. [15 pt]
Hint: You can follow the proof structure in part a).
5.Programming [40 pt]
Make sure to write your name and BU ID in a comment at the top of the program,
along with your collaborator’s name and BU ID, if any.
a) You are given an array of integers. Suppose every integer appears twice in this
array except for one. Write a C++ program that finds the integer that occurs only
once. [20 pt]
You are given a header file and a sample test program. Your job is to implement the
function findSingle. Your program must compile and run on the lab computers
using the command-line interface as follows.
> g++ -std=c++11 (-o myProgram) testProblem5a.cpp Problem5a.cpp
Submit your solution in a single file Problem5a.cpp. The most efficient solution(s)
will receive an extra credit of 0.1 point for the final class grade (out of 100).
b) Write a C++ program that keeps summing the digits of a positive integer until the
sum becomes a single digit. [20 pt]
Example:
Input: 12345
Output: 6
Explanation: 1+2+3+4+5 = 15 à 1+5 = 6
Another example:
Input: 982018
Output: 1
 Explanation: 9+8+2+0+1+8 = 28 à 2+8 = 10 à 1+0 = 1
Again, you are given a header file and a sample test program. Your job is to
implement the function sumDigit. Similar to a), your program must compile and run
on the lab computers using the command-line interface as follows.
> g++ -std=c++11 (-o myProgram) testProblem5b.cpp Problem5b.cpp
Submit your solution in a single file Problem5b.cpp. The most efficient solution(s)
will receive an extra credit of 0.1 point for the final class grade (out of 100).