Q: We temporarily cannot solve the second problem in exercise 2.1. We find it strange that F1 = |A−1|, and cannot come up with a proper explanation for A−1.

-->  Well, A_{-1} obviously does not exist. We said |A_n| = F_{n+2} for n >= 0. You have to work around to avoid A_{-1} from appearing.


Q: Can we prove the exercise 2.1. and exercise 2.2. by some other methods or some mathematical tools?


--> Well, you have an explicit formula for F_n in terms of phi_1 and phi_2, right? You could plug it in and hope for the best... Just one example; maybe you find more ways.


Q: How to find the eigenvector of a matrix without first calculating the eigenvalue?

--> Usually you don't; but I'm not an expert in "computational linear algebra"; maybe there are some algorithms that directly compute the eigenvector, and then the eigenvalue is easily obtainable from the eigenvector. I simply don't know.


Q: Can exercise2.4 be proved by the counter-evidence method?

--> You mean by "proof by contradiction"? Hmmmmm, I guess almost every proof can be made into a proof by contradiction if you want. But in my opinion it's bad style. If one can convert a proof by contradiction into a "direct" proof, one should do it.


Q: Is there any other combinatorial method can generate Fibonacci numbers? I search in Google and find two: F (n) =number of compositions of n − 1 with no part greater than 2; e.g. F (4) = 3 because we have 3 = 1 + 1 + 1 = 1 + 2 = 2 + 1.
F (n) = number of compositions of n into odd parts; e.g. F (6) counts 1 + 1 + 1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1.

--> Yes, you answered it yourself. We can count the number of ways to write n as a sum of 1 and 2, where the order matters. Formally, 

B_n = { x in {1,2}^* | sum x_i = n }

so 

B_3 = { (111) (12) (21) }
B_4 = { (1111) (112) (121) (211) (22)}
B_5 = { (11111) (1112) (1121) (1211) (122) (2111) (212) (221)  }

and so on. You can think about why this is also the Fibonacci numbers.

Q: Instead of asking "when, on average does the first 11" appear, we could ask, "when, on average, does the k-th 11 appear". For "10" instead of "11" this is simple, since the occurrences of "10" don't overlap; so for the k-th "10" you have to wait k times as long as for the first "10". But for "11" this reasoning fails. 

--> I love that question. From the top of my head, I don't know an answer. I guess you could draw an automaton (with 2k states in that case, maybe?) and get a recursive solution (recursive over k). With some luck, you can guess a solution and prove it by induction.  


Q: In the previous lectures, we find that many proofs are based on visualized or concretized approach. Do we have some general thinking or method for discrete mathematics?

--> To some extent, yes. There is a bag of techniques and tricks, like "re-interpreting your combinatorial object" in the "parliament / committee / speaker" fashion; tricks like using a function (1+x)^n and computing derivatives (this extends into a whole theory called "generating functions"); but things are not as systematic as in other fields of maths. Many methods are ad-hoc (you come up with them for a specific problem). 

I think a valuable thing to learn would be to feel fluent in both the "visual" thinking (parliament / committee / speaker / ...) and the "formal" (summation, derivatives) and easily switch between them. 



Q: Concerning exercise 2.4, if we have a series {F_n}, is there a unique way (a,f,k) to define the sequence? 

--> Obviously not! Consider the sequence

S_0 = 0
S_1 = 1
S_2 = 1
S_n = 2*S_{n-2} + S_{n-3} for n >= 3

What is this? Well, it's the Fibonacci numbers, of course! So the Fibonacci numbers can be defined by k=2, a=(1,1), and f=(0,1).

They can be defined by k=3, a=(0,2,1), f=(0,1,1) 

But the question still makes sense: note that the recurrence for S gives us the characteristic polynomial

x^3 - 2*x - 1 

This factors into

(x^2 - x - 1) * (x + 1)

The first is the characteristic polynomial of the Fibonacci numbers; the second is linear and has only -1 as root (so it's obviously the "wrong" root).

So we can ask whether there is a "unique simplest" recurrence that defines the sequence. By "simplest" let's say "the one with smallest k".

I conjecture *yes*. Can you prove it? Can you disprove it?