Table of Contents

Common Sequences

• $1 + 2 +3+...+N = \boldsymbol{\frac{N(N+1)}{2}}$
  • Derivation
    1. Pair each number with its opposite at the end of the sequence.
       • If there aren’t enough numbers to pair everyone, start with 0.
    2. You end up with $\frac{N+1}{2}$ pairs, and each pair adds up to N.
    3. Multiply the number of pairs by the sum of each pair to get the total sum.
  • Example
    • $1 + 2 + 3 + 4 + 5$
    • $(0 + 5) + (1 + 4) + (2 + 3)$
      • $\frac{N+1}{2} = 3$ pairs
      • N = 5 per pair
    • $(3)(5) = 15$
      • $\frac{N(N+1)}{2} = 15$ total
• $20 + 21 + 22 + ... + 2n = 2n + 1 − 1$
  • The sum of a sequence of 2is is roughly equal to the next number in the sequence.
    • $2^0 + 2^1 + ... + 2^{99} ≈ 2^{100}$
  • Derivation
    1. Convert each number to binary form.
       • A power of 2 corresponds to a 1 in that digit/place.
       • $2^0 = 1$
       • $2^1 = 10$
       • $2^2 = 100$
    2. Sum them up. The result will be all 1’s
       • $2^0 + 2^1 + 2^2 = 1 + 10 + 100 = 111$
    3. Convert the binary number back to decimal.
       • $111 = 24 − 1 = 15$
       • The lowest number you can represent with n bits is 2n (all 0’s). The highest number is 2n − 1 (all 1’s).
         • $0000 = 24 = 16$

Logarithms

• Converting between log bases
  • $\frac{\log_2 C}{\boldsymbol{\log_2 10}} = \log_{10} C$
  • To convert from base 2 log to a base 10 log, divide by a constant value: $log_210$.
    • The old base is the subscript.
    • The new base is the argument.

Permutations & Combinations

Permutations

• Permutations tell you every possible ordering you can make with a bank of n unique items to choose from.
  • Most common permutation questions involve finding how many ways you can rearrange a string.
  • Caveat: the items must be unique, i.e. you can’t reuse items.
• To find all possible orderings of n characters (using all characters)
  • $n! = (n)(n − 1)(n − 2)(...)(1)$
  • Derivation
    • You have n choices for the first character.
    • You have $n − 1$ choices for the next character, because one of them has been used.
    • For the last character, you only have one choice.
• To find all possible orderings of a specific size (r), built by choosing out of a bank of n characters:
  • $\boldsymbol{nPr = \frac{n!}{(n-r)!}}=(n)(n-1)(n-2)(...)(n-r+1)$
  • This is the same as before, except you’re cutting it off early.
    • After you choose all r characters for your ordering, you still have some left in the bank $(n − r + 1)$.
  • Derivation
    1. Find every possible ordering you can make with the bank of characters
       • $n!$
    2. After the first r characters have been chosen, cut off the future choices. Do this by dividing by $(n − r)$!
       • $\frac{n!}{(n-r)!}$

Combinations

• Combinations tell you every possible group or subset you can make with a bank of n unique items, where ordering doesn’t matter.
  • abcd and dcba are duplicate combinations. Only 1 is counted.
• To find every possible subset of size r you can make from a bank of n items:
• $\boldsymbol{{n \choose r} = \frac{nPr}{r!}} = \frac{n!}{r!(n-r)!}$
• ${5 \choose 5} = 1$. Only one possible subset, because orderings only count once.
• Derivation

1. Find every possible ordering you can make.
   • nPr
2. Find how many duplicates each ordering has.
   • Each subset can be ordered in r! different ways. You have r choices for the first item, r − 1 for the next, …