FIT CTU Course Pages
BIE-VAK — Selected Combinatorics Applications
Go to course navigation

1. Mathematical Induction

In the first homework for this subject, we return to the first seminar, where we covered how not to do proofs. This homework gives you a chance to practice one of the techniques that weren’t presented in the best light. In particular, it will be about mathematical induction, and since you already know how not to prove claims by induction, it will certainly be a piece of cake for you.

Instructions

  • You can find a column "Task ID" in the Grades application.
  • This number corresponds to the task you should solve.
  • Read the task and solve it by yourself.
  • Then, send scanned and hand-written solution as a single PDF file using MS Teams.
  • The deadline for submission is February 27, 2024, 23:55:00. The deadline is strict.
Warning:

Follow the instructions. If you do not meet any of the points, your solution will be rejected.

Tasks

Task 1

Estimate the result of the following sum for every n≥1n \geq 1 and use mathematical induction to prove the correctness of your estimate.

∑i=1n2i\sum_{i=1}^n 2^i
Task 2

Estimate the result of the following sum for every n≥1n \geq 1 and use mathematical induction to prove the correctness of your estimate.

∑i=1ni\sum_{i=1}^n i
Task 3

Using mathematical induction, prove that the following equality holds for every n≥1n \geq 1

∑i=1ni⋅2i=(n−1)⋅2n+1+2\sum_{i=1}^n i\cdot 2^i = (n-1)\cdot 2^{n+1} + 2
Task 4

Using mathematical induction, prove that the following equality holds for every n≥1n \geq 1.

∑i=1ni(i+1)=n(n+1)(n+2)3\sum_{i=1}^n i(i+1) = \frac{n(n+1)(n+2)}{3}
Task 5

Using mathematical induction, prove that the following equality holds for every n≥1n \geq 1.

∑i=1n(2i−1)=n2\sum_{i=1}^n (2i-1) = n^2
Task 6

Using mathematical induction, prove that the following equality holds for every n≥1n \geq 1.

∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}
Task 7

Using mathematical induction, prove that the following equality holds for every n≥1n \geq 1.

∑i=1ni⋅i!=(n+1)!−1\sum_{i=1}^n i\cdot i! = (n+1)! - 1
Task 8

Using mathematical induction, prove that the following equality holds for every n>1n > 1.

∑i=1ni(i+1)(i+2)=n(n+1)(n+2)(n+3)4\sum_{i=1}^n i(i+1)(i+2) = \frac{n(n+1)(n+2)(n+3)}{4}