Discrete Sequences

Sequences

subsequences
- cant be a rearrengement of a sequence
  - can only "remove" elements from a sequence
- number of subsequences = 2^n
- consecutive
  - number = n(n+1)/2 (+1 if including empty)
    - $(\binom{n + 1}{2}) =$ choosing 2 positions to be start/end
  - {},{a},{a,b},
- non-consecutive
  - number of =
properties
- increasing
  - an+1>an
- non-increasing
- decreasing
- non-decreasing
- monotonic
  - if its either non-decreasing or non-increasing
  - always increasing or decreasing, no going the other way at any point
arithmetic sequences
- common difference between two terms ( +/- )
- $a_{n} = a_{1} + (n - 1) d$
geometric sequence
- common ratio between two terms ( x / / )
heron's method
- a sequence-based algorithm that iteratively calculates square roots
- an-1 = first guess
- x = number trying to be square rooted
newton's method
- a sequence-based algorithm that iteratively calculates square roots of functions

proof by induction
- basis step
- inductive hypothesis
  - for (domain of what is being proved), we assume (formula/sequence/recurrance relation)
- inductive conclusion
  - by IH,
proof by strong induction
- difference = can look back more than one step
- in IH -> i = 1,2,3,...,k
- in IC -> prove for k
  - all numbers before k are proved