Hand written

An infinite power series is simply an infinite sum of terms of the form cnxn were cn is some constant. So we might write a power series like this:

or expanded like this

c0+c1x+c2x2+c3x3+c4x4+c5x5+⋯.

When viewed in the context of generating functions, we call such a power series a generating series. The generating series generates the sequence

c0,c1,c2,c3,c4,c5,….

In other words, the sequence generated by a generating series is simply the sequence of coefficients of the infinite polynomial.

Ordinary Generating Functions

The ordinary generating function for the sequence (ak ) is defined be:

Example

Suppose that ak= (1, 1, 1, 0, 1, 1, …) , Then the ordinary generating function is :

Exponential Generating Function

If (ak) is any sequence, the exponential generating function :

Example

Suppose that ak= 1, k= 0,1,… . Then the exponential generating function is :

Probability Generating Function

Suppose that after an experiment is performed, it is known that one and only one of a (finite or countable infinite) set of possible events will occur. Let pk be the probability that the kth event occurs, k=0,1,2,… . The probability generating function:

Example

Suppose that the experiment is tossing a fair coin. Then the events are heads (H) and tails(T), with P0 , probability of H, equal to ½ , and P1 , probability of T, equal to ½ . Hence, the probability generating function is:

G(x) = ½ + ½ x

Explain in detail about Recurrence Relations with at least 3 examples.

Definition

A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s).

The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term. If we denote the nth term in the sequence by xn, such a recurrence relation is of the form

for some function f. One such example is xn+1=2−xn/2

A recurrence relation can also be higher order, where the term xn+1 could depend not only on the previous term xn but also on earlier terms such as xn−1, xn−2, etc. A second order recurrence relation depends just on xn and xn−1 and is of the form

xn+1=f(xn,xn−1)

for some function f with two inputs. For example, the recurrence relation xn+1=xn+xn−1 can generate the Fibonacci numbers.

To generate sequence based on a recurrence relation, one must start with some initial values. For a first order recursion xn+1=f(xn), one just needs to start with an initial value x0 and can generate all remaining terms using the recurrence relation. For a second order recursion xn+1=f(xn,xn−1), one needs to begin with two values x0 and x1. Higher order recurrence relations require correspondingly more initial values.

Suppose we have: tk+1 = 2tk

is an example of a recurrence relation. We know that t1= 1. This is given to us and is called an initial condition.

We know that:

t2 = 2t1 = 2*1=2

t3 = 2t2 = 2*2t1=4

t4 = 2t3 = 2*2t2=2*2*2t1

So in general: tk = 2tk-1 = …. = 2k-1 t1= 2k-1

Linear recurrences

1. Linear homogeneous recurrences

2. Linear non-homogeneous recurrences

Example: 

Find a recurrence relation and initial conditions for 1,5,17,53,161,485….

That they are growing by a factor 3.

1.3=3, 5.3=15, 17.3=51 and so on and end up with 2 less than the next term.

so an=3an-1+2 is the recurrence relation and the initial condition is a0=1.

Examples:

1. The Fibonacci recurrence is Fn = Fn-1 + Fn-2

Fk = Fk-1 + Fk-2 ,

F0 = F1 =1

F2 = F1 + F0 = 1+1 =2

F3 = F2 + F1 = 2+1 =3

F4 = F3 + F2 = 3+2 =5

F5 = F4 + F3 = 5+3 =8

2. Its characteristic equation is r2 - r - 1 = 0

Example 

Check that an=2n+1 is a solution to the recurrence relation an=2an−1−1with a1=3.

First, it is easy to check the initial condition: a1 should be 21+1 according to our closed formula. Indeed, 21+1=3, which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in

2an−1−1=2(2n−1+1)−1

=2n+2−1

=2n+1

=an

Example

Suppose we have: Sk+1 = Sk +2k , initial condition, S1 =1.

S2 = S1+ 21 =1+2 =3

S3 = S2+ 22 =3+4 =7

In general: Sk = Sk-1 +2k-1 = S1+ 2 + 22 + … + 2k-1