Free online math practice

Discrete mathematics identities Practice

Common counting, logic, set, graph, and recurrence identities.

Start practicingDiscrete mathematics identities

  • Free to practice.
  • No account required.
  • Progress stays on this device.

What you’ll practice

Counting, sets and logical statements use different kinds of objects. Read the domain and conditions attached to each identity before completing it.

Where this helps

Computer science, proofs, algorithms, and structured counting.

Before you start

Try the examples to see what you’ll practice. Check the answer form and any stated conditions.

Explainers

Choosing and leaving out

Choosing 2 people from 9 leaves 7 people out. Every chosen pair matches exactly one group of 7 left out. C(9, 2) = C(9, 7).

In general, C(n, k) = C(n, n − k), for integers 0 ≤ k ≤ n. Use the smaller of k and n − k when it makes a calculation shorter.

Add a finite geometric pattern

1 + 3 + 9 + 27 = 40. These are powers 3⁰ through 3³, so there are 4 terms.

For powers r⁰ through rⁿ, use Σₖ₌₀ⁿ rᵏ = (1 − rⁿ⁺¹)/(1 − r), with n a nonnegative integer and r ≠ 1. Multiplying the sum by r and subtracting cancels the middle terms. If r = 1, the sum is n + 1.

Count the multiplications from term zero

Start with a₀ = 5 and multiply by 3 each time: a₁ = 15, a₂ = 45, a₃ = 135.

For the recurrence aₙ₊₁ = raₙ, the closed form is aₙ = a₀rⁿ. The index n counts how many multiplications have happened since term zero. At n = 0, keep the initial value a₀.

Pair the first and last numbers

1 + 2 + 3 + 4 + 5 + 6 = 21. Pair the ends: 1 + 6, 2 + 5, and 3 + 4 each make 7.

For the first n positive integers, the sum is n(n + 1)/2. Each end-pair has total n + 1. The formula also works for odd n, when the middle number supplies half a pair.

Odd numbers build a square

1 + 3 + 5 + 7 + 9 = 25 = 5².

The first n positive odd numbers add to n². Each new odd number adds the next border of a square. The nth odd number is 2n − 1, so count the terms before squaring.

Add the squares of the first integers

1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30.

For positive integer n, use Σₖ₌₁ⁿ k² = n(n + 1)(2n + 1)/6. At n = 4, this is 4 × 5 × 9/6 = 30. This adds the separate squares. It does not square the sum 1 + 2 + 3 + 4.

Try a few examples

Real practice. Real progress.

Example 1 of 4

n and k are integers with 0 ≤ k ≤ n.

Choose the exact expression.

Grades and courses that include this topic

Related practice

Start practicingDiscrete mathematics identities

  • Free to practice.
  • No account required.
  • Progress stays on this device.