Question
Transcribed Text
1. Prove the summation formula for all natural numbers n using induction:
∑
1
𝑘(𝑘 + 1)
𝑛
𝑘=1
= 1 −
1
𝑛 + 1
2. Prove the inequality for all natural numbers n using induction:
log2 𝑛 < n
Hint: you may find the following identity helpful: 𝑛 + 1 = 𝑛(1 + 1
𝑛
). You can use without
proof that log2 𝑛 is a strictly increasing function.
3. Prove using structural induction that every member of the following recursively defined set
𝑆 has a remainder of 1 when divided by 5:
1 ∈ 𝑆
𝑛 ∈ 𝑆 → 5𝑛 + 1 ∈ 𝑆
𝑛 ∈ 𝑆 → 𝑛2 ∈ 𝑆
4. Find a closed-form representation of the following recursively defined sequence and show
your work:
𝑎0 = 1, 𝑎1 = 2,
𝑎𝑛+2 = 𝑎𝑛+1 + 2𝑎𝑛
5. Find a closed-form representation of the following recursively defined sequence and show
your work:
𝑎0 = 0, 𝑎1 = 0, 𝑎2 = −2, 𝑎3 = 0
𝑎𝑛+4 = −2𝑎𝑛+2 − 𝑎n
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
Return to homework library