File Details:

Questions:

1. Consider the function f: N->N, recursively given by f(0)=1 and f(n+1)=2-f(n). Find f(10).
2. How many Lattice paths start as (3, 3) and end at (10, 10)?
3. Prove that the maximum number of nodes in a binary tree of depth a is 2^a - 1, where a 1.
4. Show that the set M of all elements {0, 1, 2, 3, 4, 5} with addition modulo 6 and multiplication modulo 6 as a composition is a ring with zero divisors.
5. Show that the set M of all matrices of the form [[1, n], [0, 1]] where n Z is a semigroup under multiplication and it is isomorphic to (Z, +).
6. Prove that the product of two lattices is a lattice.
7. State and prove DeMorgan's law of Boolean Algebra.
8. Find the order of the elements of (Z_8, +_8).
9. Define multigraph with an example.
10. Use a membership table to show that: A (B C) = (A B) (A C).
11. Show that there are only two non-isomorphic groups of order 4.
12. Show that in a Boolean algebra, the idempotent laws X X = X and X X = X hold for every element X.
13. Give an example of a graph which is Hamiltonian but not Eulerian and vice-versa.
14. Define K-regular graph. Give examples of 2-regular, 3-regular, and 4-regular graphs.
15. Show that the function f(x, y) = x + y is primitive recursive.
16. Use mathematical induction to show that k^2 = (n(n+1)(2n+1))/6 for k = 1 to n.
17. State and prove the pigeonhole principle.
18. Define minimum spanning tree.
19. Negate the statement: Every city in Canada is clean.
20. Prove that a simple graph has a spanning tree if and only if it is connected.
21. If a group has four elements, show that it must be abelian.