Linear Algebra: Sequences

Product sequence, Summation sequence, factorials.

26 flashcards · Mathematics · by lakesare

1. Rewrite by separating off the final term.

2. Transform the following summation to use j = k + 1.

   First calculate the lower and upper limits of the new summation: When k = 0, j = k + 1 = 0 + 1 = 1. When k = 6, j = k + 1 = 6 + 1 = 7. Thus the new sum goes from j = 1 to j = 7.

3. Simplify:

4. Simplify:

5. How is this symbol read?

   n choose r

6. What do n and r mean here?

   n - number of elements in a set r - number of elements of each subset that to be chosen from this set

7. What does n choose r signify?

   Number of subsets of size r that can be chosen from a set with n elements. Many electronic calculators have keys for computing values of n r  . These are denoted in various ways such as nCr, C(n,r), nCr, and Cn,r. The letter C is used because the quantities n r  are also called combinations. Sometimes they are referred to as binomial coefficients because of the connection with the binomial theorem

8. What's the formula for n choose r?

9. Compute:

10. Compute:

    The fact that 0! = 1 makes this formula computable. It gives the correct value because a set of size 4 has exactly one subset of size 4, namely itself.

11. How is this read: 3!

    3 factorial

12. Find an explicit formula for a sequence that has the following initial terms:

    An explicit formula or general formula for a sequence is a rule that shows how the values of ak depend on k.

13. Give formula for Sum of the First n Integers: 1 + 2 + 3 + ··· + n.

14. What is geometric progression?

    Geometric sequence/progression is a sequence where each next member is r times bigger than the previous member: A geometric sequence is a sequence such that any element after the first is obtained by multiplying the preceding element by a constant called the common ratio which is denoted by r. a is the first term.

15. Denote a SUM of a geometric sequence/progression (without the formula itself).

16. Name 3 ways in which sequences can be defined/written.

    Via listing members: Via the explicit formula for nth term: 3. Via recursion: Unfortunately, misunderstandings can occur when this approach is used. The next term of the sequence could be 9 if we mean a sequence of odd integers, or it could be 11 if we mean the sequence of odd prime numbers. The advantage of defining a sequence by such an explicit formula is that each term of the sequence is uniquely determined and can be computed in a fixed, finite number of steps, by substitution. Sometimes i…

17. Note that defining sequences recursively is similar to proving theorems by mathematical induction. The recurrence relation is like the inductive step and the initial conditions are like the basis step.

    Indeed, the fact that sequences can be defined recursively is equivalent to the fact that mathematical induction works as a method of proof.

18. Define a sequence c0, c1, c2,... recursively as follows: For all integers k ≥ 2, Find c2, c3, c4.

    c2 = 5. c3 = 12. c4 = 33.

19. How would you go about showing that this sequence: satisfies the recurrence relation:

    We need to find Ck and Ck-1 using the sequence. After that, substitute Ck and Ck-1 into our recurrence relation, and show that it holds true!

20. Probably the most difficult part of solving problems recursively is to figure out how knowing the solution to smaller subproblems of the same type as the original problem will give you a solution to the problem as a whole.

    You suppose you know the solutions to smaller subproblems and ask yourself how you would best make use of that knowledge to solve the larger problem. The supposition that the smaller subproblems have already been solved has been called the recursive paradigm or the recursive leap of faith. Once you take this leap, you are right in the middle of the most difficult part of the problem, but generally, the path to a solution from this point, though difficult, is short. The recursive leap of faith i…

21. What is arithmetic sequence/progression?

    A sequence in which each term equals the previous term plus a fixed constant, is called an arithmetic sequence.

22. Arithmetic sequence VS geometric sequence?

    Arithmetic sequence: Geometric sequence:

23. Let r be a fixed nonzero constant, and suppose a sequence a0, a1, a2, ... is defined recursively as follows: Use iteration to guess an explicit formula for this sequence.

    It's a geometric sequence, btw!

24. Suppose Kn is the amount of edges that get produced by adding one more vertice: First find a recurrence relation that describes Kn Then guess an explicit formula for Kn.

    Observe that K5 may be obtained from K4 by adding one vertex and drawing edges between this new vertex and all the vertices of K4 (the old vertices): 1. Recurrence relation and initial terms: 2. Explicit formula:

25. Prove the following statement: What does it mean to show the correctness of a formula for a recursively defined sequence? Given a sequence of numbers that satisfies a certain recurrence relation and initial condition, your job is to show that each term of the sequence satisfies the proposed explicit formula.

    P(1) is true. 2. For all integers k ≥ 1, if P(k) is true then P(k + 1) is also true.

26. Explain each word: A second-order - ? linear - ? homogeneous - ? recurrence relation with constant coefficients is a recurrence relation of the form ak = Aak−1 + Bak−2 for all integers k ≥ some fixed integer, where A and B are fixed real numbers with B = 0.

    second-order - has ak-1 and ak-2 linear - ak−1 and ak−2 appear in separate terms and to the first power homogenous - there is no constant term “Second-order” refers to the fact that the expression for ak contains the two previous terms ak−1 and ak−2,“linear” to the fact that ak−1 and ak−2 appear in separate terms and to the first power,“homogeneous” to the fact that the total degree of each term is the same (thus there is no constant term), and“constant coefficients” to the fact that A and B ar…