Discrete! #33: Discrete Mathematics and Its Applications 2.4 Part A

2.4: Sequences and Summations

My general sense on this sections is that the real action is in problem-solving, since summations and sequences are conceptually pretty easy. So, I’m gonna be a bit breezy here and then we can get into more depth with the problem sets. If you’ve been following along with the calc posts, you’re already pretty up on this stuff.

Introduction

BOOK DEFINITION:

“A sequence is a function from a subset of the set of integers (usually te set {0,1,2,…} pr the set {1,2,3,…} to a set S. We use the notation to denote the image of the integer n. We call a term of the sequence.”

I think that’s pretty clear. If your sequence is then the output is just the list “2,4,6,8,10,…”

So, is basically saying “Make a list such at a at each position 1 to infinity is given by 2*(that position).”

Special Integer Sequences

Just because you recognize a pattern in a sequence doesn’t mean you know how to denote it with a pretty function like the one above. If you’re a dork, you’ve probably come across riddles about predicting the next element of a sequence.

The book gives a slightly tricky one. Conjecture a formula for {1,7,25,79,241,727,2185,6559,19681,59047}

Now, although can’t instantly say what it is, you can try some things. Is there the same difference between consecutive digits? Nope. How about a constant multiplier between digits? Nope. You step back a second, and you notice it contains prime numbers like 7 and 29. So, at the least, there’s probably some addition or subtraction. You also see that the numbers grow quickly, so we’re probably talking about some sort of exponentiation here.

After some fiddling, you’ll see that you square n then subtract 2.

Of course, there’s no one right way to do this. But, you want to get some methods of attack to be intuitive.

Summation

A summation is just a sum of the elements of a sequence over a certain interval.

is a pretty typical way to write out a summation.

The i is just the variable. The =1 just means that for the series we’re about to sum, we use {1,2,3,…}. If it’d been i=0, we’d have used {0,1,2,3…}. You could set some other starting point, but it’s fairly rare. The n at the top is where you end. So, if i=1 and n is 5, you care about the values of a at {1,2,3,4,5}.

I have to say, it always seemed to me like it’d be more clear to write something like , but perhaps there’s a good reason not to.

In any case, the idea is pretty simple. A summation is the sum of a sequence over a given interval.

The book goes on to give some examples, including a proof of the geometric series. It’s probably worth your time to go over, and I don’t really have anything to add here.

My general feeling on these things is it doesn’t help to try to memorize these things outright. You remember them if you use them regularly. In general, what’s good is to have intuition about these things. Seeing a function or list of numbers, it’s useful to be able to say “That feels exponential.” or “That feels sinusoid.”

Last, they get to infinite series. As you may know from calc, an infinite series is just the sum of an infinite sequence. If this sounds weird, remember that a lot of sequences start to get to really small numbers really quickly. For example, if the function you’re worried about is 1/x!, as the sequence gets bigger and bigger, the function’s output gets smaller than smaller. Pretty quickly, you’ve got some number right around 2.71812 or so. Often, you can get a simple formula for the sum.

Next Stop: Cardinality