Fibonnaci and binomial coefficient
- Thread starter iteg
- Start date
D
Deleted member 4993
Guest
Please share your work/thoughts about this assignment.
Have you tried method of induction?
Please follow the rules of posting in this forum, as enunciated at:
READ BEFORE POSTING
D
Deleted member 4993
Guest
What attempts did you make to solve this problem?
What is your strategy to solve this problem?
Yes. Some of us prefer defining the natural numbers as starting with 0 rather than 1. So the notation of [MATH]N_0[/MATH]is designed to avoid confusion about which definition is being used.
Here is a partial quotation from wikipedia https://en.wikipedia.org/wiki/Natural_number:
In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country"). In common mathematical terminology, words colloquially used for counting are "cardinal numbers" and words connected to ordering represent "ordinal numbers". The natural numbers can, at times, appear as a convenient set of codes (labels or "names"); that is, as what linguists call nominal numbers, forgoing many or all of the properties of being a number in a mathematical sense.
Some definitions, including the standard ISO 80000-2,[1] begin the natural numbers with 0, corresponding to the non-negative integers 0, 1, 2, 3, …, whereas others start with 1, corresponding to the positive integers 1, 2, 3, ….[2][3][4][5] Texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, but in other writings, that term is used instead for the integers (including negative integers).
Last edited:
yes i do know that method, but where will i do the induction? i mean which is the mathematical notation i can start with by taking the base case.
on the sum from 0 to n of
n-k
k
? i just wanna know with where will i apply the induction hypothesis
thanks
on the sum from 0 to n of
n-k
k
? i just wanna know with where will i apply the induction hypothesis
thanks
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,596
Based on your post I am not sure if you understand sigma notation. Do you?
Before you can do an induction proof you need to know what you are trying to prove. To save time I will tell you what you are trying to show
Now show that this equal sign is valid for n=0 (NOT n=2)
Jomo
I have played around with this a bit and have found it harder than it looks. The Fibonacci series is generated by a sum of two numbers. I strongly suspect that in the first step we prove for
[MATH]F_{0+1} \text { and } F_{0+2}.[/MATH]
It is fairly easy to show that
[MATH]F_{0+1} = F_1 = \dbinom{0 - 0}{0} = \sum_{k=0}^{0} \dbinom{0 - k}{k}.[/MATH] and
[MATH]F_{0+2} = F_2 = \dbinom{1 - 0}{0} + \dbinom{1 - 1}{1} = \sum_{k=0}^{0 + 1} \dbinom{0 + 1 - k}{k}.[/MATH]
This provides the logical basis to show the existence of a non-empty set [MATH]\mathbb J[/MATH] such that
[MATH]j \in \mathbb J \implies j \in \mathbb N_0, \ F_{j+1} = \sum_{k=0}^j \dbinom{j - k}{k}, \text { and } F_{j+2} = \sum_{k=0}^{j+1} \dbinom{(j + 1) - k}{k}.[/MATH]
From there, it is a cinch to show that
[MATH]F_{(j+1)+1} = F_{j+2} \sum_{k=0}^{j+1} \dbinom{(j+1) - k}{k}.[/MATH]
But notice that we need F_{j+2}, which means, I think, we need F_{(j+1)+2}, which I have not found easy. In fact I haven't yet found it at all.
A follow-up. As may have been inferred, I do not have a lot of time right now to devote to finding a proof so I cannot give the OP a definite hint.
However, the following may be helpful.
The high order terms of the sums (except for F_1) are zeroes. Moreover, the number of zero terms may depend on whether
the i in F_i is even or odd. Finally, when we add
[MATH]F_{j+1} + F_{(j+1)+1} = F_{(j+1)+2}[/MATH]
the sums involved do not have the same number of terms.
Maybe over the weekend, I shall have more time. In the meantime, I hope this gives some useful clues to the OP.
However, the following may be helpful.
The high order terms of the sums (except for F_1) are zeroes. Moreover, the number of zero terms may depend on whether
the i in F_i is even or odd. Finally, when we add
[MATH]F_{j+1} + F_{(j+1)+1} = F_{(j+1)+2}[/MATH]
the sums involved do not have the same number of terms.
Maybe over the weekend, I shall have more time. In the meantime, I hope this gives some useful clues to the OP.
This has taken me an unconscionable length of time. My only excuse is that I have had other things to do.
[MATH]\text {Lemma I: } u \in \mathbb N_0, \ v \in \mathbb N_0 \text { and } 0 \le v \le u \implies[/MATH]
[MATH]\dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{u + 1 - v}{v + 1}.[/MATH]
Proof
[MATH]0 \le v \le u \implies 0 \le v < \dfrac{u}{2},\ 0 \le v = \dfrac{u}{2}, \text { or } v > \dfrac{u}{2} \ge 0.[/MATH]
[MATH]\text {Case A: } v > \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v > u \implies v > u - v,\ v + 1 > u - v, \text { and } v + 1 > u + 1 - v.[/MATH]
[MATH]\therefore \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = 0 + 0 = 0 = \dbinom{u + 1 - v}{v + 1}.[/MATH]
[MATH]\text {Case B: } v = \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v = u \implies v = u - v,\ v + 1 = u + 1 - v, \text { and } v + 1 > u - v = v.[/MATH]
[MATH]\therefore \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{v}{v} + 0 =[/MATH]
[MATH]1 + 0 = 1 = \dbinom{v + 1}{v + 1} = \dbinom{u + 1 - v}{v + 1} .[/MATH]
[MATH]\text {Case C: } v < \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v < u \implies v < u - v,\ v + 1 \le u - v, \text { and } v + 1 < u + 1 - v.[/MATH]
[MATH]\dbinom{u - v}{v} = \dfrac{(u - v)!}{v! * (u - 2v)!} = \dfrac{(v + 1) * (u - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u - v}{v + 1} = \dfrac{(u - v)!}{(v + 1)! * (u - 2v - 1)!} = \dfrac{(u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u + 1 - v}{v + 1} = \dfrac{(u + 1 - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dfrac{(v + 1) * (u - v)!}{(v + 1)! * (u - 2v)!} + \dfrac{(u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!} =[/MATH]
[MATH]\dfrac{(v + 1 + u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!} = \dfrac{(u + 1 - v) * (u - v)!}{(v + 1)! * (u - 2v)!} =[/MATH]
[MATH]\dfrac{(u + 1 - v)!}{(v + 1)! * (u - 2v)!} = \dbinom{u + 1 - v}{v + 1}.[/MATH]
[MATH]\text {Thus, in all three cases } \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{u + 1 - v}{v + 1} \text { Q.E.D.}[/MATH]
[MATH]\text {Lemma II: }\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v}.[/MATH]
Proof
[MATH]\sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} = \dbinom{u + 1 - 0}{0} + \sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v} = 1 + \sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v}.[/MATH]
[MATH]w + 1 = v \implies w = 0 \text { if } v = 1 \text { and } u + 1 - v = u + 1 - (w + 1) = u - w \implies[/MATH]
[MATH]\sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v} = \sum_{w=0}^u \dbinom{u - w}{w + 1}.[/MATH]
[MATH]\sum_{v=0}^u \dbinom{u - v}{v} = \sum_{w=0}^u \dbinom{u - w}{w}.[/MATH]
[MATH]\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =[/MATH]
[MATH]\left ( \sum_{w=0}^u \dbinom{u - w}{w} \right ) + 1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w + 1} \right ) =[/MATH]
[MATH]1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w} \right ) + 1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w + 1} \right ) =[/MATH]
[MATH]1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w} + \dbinom{u - w}{w + 1} \right )=[/MATH]
[MATH]1 + \sum_{w=0}^u \dbinom{u + 1 - w}{w + 1} \text { by Lemma I.}[/MATH]
[MATH]w + 1 = v \implies u + 1 - w = u + 1 - (v - 1) = u + 2 - v \implies[/MATH]
[MATH]1 + \sum_{w=0}^u \dbinom{u + 1 - w}{w + 1} = 1 + \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v}.[/MATH]
[MATH]\therefore \left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =[/MATH]
[MATH]1 + \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} = 1 + \left ( \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} \right ) + 0 =[/MATH]
[MATH]1 + \left ( \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} \right ) + \dbinom{u + 2 - (u + 2)}{u + 2} =[/MATH]
[MATH]1 + \sum_{v=1}^{u+2} \dbinom{u + 2 - v}{v} = \dbinom{u + 2 - 0}{0} + \sum_{v=1}^{u+2} \dbinom{u + 2 - v}{v} =[/MATH]
[MATH]\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v}. \text{ In short,}[/MATH]
[MATH]\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v} \text { Q.E.D.}[/MATH]
And now, at last, we are ready for our induction proof, which, as a result of Lemma 2, has become quite straight forward..
We define the Fibonacci numbers as:
[MATH]F_0 = 0,\ F_1 = 1, \text { and } F_{n+2} = F_n + F_{n+1} \text { if } n \ge 2.[/MATH]
The theorem is:
[MATH]\text {Theorem: } n \in N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n- k}{k}.[/MATH]
Proof
[MATH]F_{0+1} = F_1 = 1 = \dbinom{0}{0} = \dbinom{0 - 0}{0} = \sum_{k=0}^0 \dbinom{0 - k}{k}.[/MATH]
[MATH]F_{0 + 2} = F_2 = F_0 + F_1 = 0 + 1 = 1 + 0.[/MATH]
[MATH]\therefore F_{0+2} = \dbinom{1}{0} + 0 = \dbinom{1 - 0}{0} + \dbinom{1 - 1}{1} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k}.[/MATH]
[MATH]\therefore \exists \text { a non-empty set } \mathbb J \text { such that any } j \in \mathbb J \implies [/MATH]
[MATH]j \in \mathbb N_0, \ F_{j+1} = \sum_{k=0}^j \dbinom{j - k}{k}, \text { and } F_{j+2} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k}.[/MATH]
[MATH]\text {For induction, we must show first that } F_{(j+1)+1} = \sum_{k=0}^{j+1} \dbinom{(j + 1) - k}{k}.[/MATH]
[MATH]F_{(j+1)+1} = F_{j+2} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k} = \sum_{k=0}^{j+1} \dbinom{(j + 1) - k}{k}.[/MATH]
[MATH]\text {That now done, we must next show that } F_{(j+1)+2} = \sum_{k=0}^{(j+1)+1} \dbinom{(j + 1) + 1 - k}{k}.[/MATH]
[MATH](j + 1) + 2 = j + 3 \ge 2 \ \because \ j \in \mathbb N_0.[/MATH]
[MATH]\therefore F_{(j+1)+2} = F_{j+1} + F_{(j+1)+1} = F_{j+1} + F_{j+2} \implies[/MATH]
[MATH]F_{(j+1)+2} = \left ( \sum_{k=0}^j \dbinom{j - k}{k} \right ) + \left ( \sum_{k=0}^{j+1} \dbinom{j +1 - k}{k} \right ) \implies[/MATH]
[MATH]F_{(j+1)+2} = \sum_{k=0}^{j+2} \dbinom{j + 2 - k}{k} \text { by Lemma II.}[/MATH]
[MATH]\therefore F_{(j+1)+2} = \sum_{k=0}^{(j+1) + } \dbinom{(j + 1) + 1 - k}{k}[/MATH]
[MATH]\text {By induction, } n \in \mathbb N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n - k}{k} \text { and } F_{n+2} = \sum_{k=0}^{n+1} \dbinom{n + 1 - k}{k}.[/MATH]
[MATH]\therefore n \in \mathbb N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n - k}{k} \text { Q. E. D}[/MATH]
[MATH]\text {Lemma I: } u \in \mathbb N_0, \ v \in \mathbb N_0 \text { and } 0 \le v \le u \implies[/MATH]
[MATH]\dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{u + 1 - v}{v + 1}.[/MATH]
Proof
[MATH]0 \le v \le u \implies 0 \le v < \dfrac{u}{2},\ 0 \le v = \dfrac{u}{2}, \text { or } v > \dfrac{u}{2} \ge 0.[/MATH]
[MATH]\text {Case A: } v > \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v > u \implies v > u - v,\ v + 1 > u - v, \text { and } v + 1 > u + 1 - v.[/MATH]
[MATH]\therefore \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = 0 + 0 = 0 = \dbinom{u + 1 - v}{v + 1}.[/MATH]
[MATH]\text {Case B: } v = \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v = u \implies v = u - v,\ v + 1 = u + 1 - v, \text { and } v + 1 > u - v = v.[/MATH]
[MATH]\therefore \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{v}{v} + 0 =[/MATH]
[MATH]1 + 0 = 1 = \dbinom{v + 1}{v + 1} = \dbinom{u + 1 - v}{v + 1} .[/MATH]
[MATH]\text {Case C: } v < \dfrac{u}{2}.[/MATH]
[MATH]\therefore 2v < u \implies v < u - v,\ v + 1 \le u - v, \text { and } v + 1 < u + 1 - v.[/MATH]
[MATH]\dbinom{u - v}{v} = \dfrac{(u - v)!}{v! * (u - 2v)!} = \dfrac{(v + 1) * (u - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u - v}{v + 1} = \dfrac{(u - v)!}{(v + 1)! * (u - 2v - 1)!} = \dfrac{(u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u + 1 - v}{v + 1} = \dfrac{(u + 1 - v)!}{(v + 1)! * (u - 2v)!}.[/MATH]
[MATH]\dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dfrac{(v + 1) * (u - v)!}{(v + 1)! * (u - 2v)!} + \dfrac{(u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!} =[/MATH]
[MATH]\dfrac{(v + 1 + u - 2v) * (u - v)!}{(v + 1)! * (u - 2v)!} = \dfrac{(u + 1 - v) * (u - v)!}{(v + 1)! * (u - 2v)!} =[/MATH]
[MATH]\dfrac{(u + 1 - v)!}{(v + 1)! * (u - 2v)!} = \dbinom{u + 1 - v}{v + 1}.[/MATH]
[MATH]\text {Thus, in all three cases } \dbinom{u - v}{v} + \dbinom{u - v}{v + 1} = \dbinom{u + 1 - v}{v + 1} \text { Q.E.D.}[/MATH]
[MATH]\text {Lemma II: }\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v}.[/MATH]
Proof
[MATH]\sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} = \dbinom{u + 1 - 0}{0} + \sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v} = 1 + \sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v}.[/MATH]
[MATH]w + 1 = v \implies w = 0 \text { if } v = 1 \text { and } u + 1 - v = u + 1 - (w + 1) = u - w \implies[/MATH]
[MATH]\sum_{v=1}^{u+1} \dbinom{u + 1 - v}{v} = \sum_{w=0}^u \dbinom{u - w}{w + 1}.[/MATH]
[MATH]\sum_{v=0}^u \dbinom{u - v}{v} = \sum_{w=0}^u \dbinom{u - w}{w}.[/MATH]
[MATH]\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =[/MATH]
[MATH]\left ( \sum_{w=0}^u \dbinom{u - w}{w} \right ) + 1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w + 1} \right ) =[/MATH]
[MATH]1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w} \right ) + 1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w + 1} \right ) =[/MATH]
[MATH]1 + \left ( \sum_{w=0}^u \dbinom{u - w}{w} + \dbinom{u - w}{w + 1} \right )=[/MATH]
[MATH]1 + \sum_{w=0}^u \dbinom{u + 1 - w}{w + 1} \text { by Lemma I.}[/MATH]
[MATH]w + 1 = v \implies u + 1 - w = u + 1 - (v - 1) = u + 2 - v \implies[/MATH]
[MATH]1 + \sum_{w=0}^u \dbinom{u + 1 - w}{w + 1} = 1 + \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v}.[/MATH]
[MATH]\therefore \left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =[/MATH]
[MATH]1 + \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} = 1 + \left ( \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} \right ) + 0 =[/MATH]
[MATH]1 + \left ( \sum_{v=1}^{u+1} \dbinom{u + 2 - v}{v} \right ) + \dbinom{u + 2 - (u + 2)}{u + 2} =[/MATH]
[MATH]1 + \sum_{v=1}^{u+2} \dbinom{u + 2 - v}{v} = \dbinom{u + 2 - 0}{0} + \sum_{v=1}^{u+2} \dbinom{u + 2 - v}{v} =[/MATH]
[MATH]\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v}. \text{ In short,}[/MATH]
[MATH]\left ( \sum_{v=0}^u \dbinom{u - v}{v} \right ) + \left ( \sum_{v=0}^{u+1} \dbinom{u + 1 - v}{v} \right ) =\sum_{v=0}^{u+2} \dbinom{u + 2 - v}{v} \text { Q.E.D.}[/MATH]
And now, at last, we are ready for our induction proof, which, as a result of Lemma 2, has become quite straight forward..
We define the Fibonacci numbers as:
[MATH]F_0 = 0,\ F_1 = 1, \text { and } F_{n+2} = F_n + F_{n+1} \text { if } n \ge 2.[/MATH]
The theorem is:
[MATH]\text {Theorem: } n \in N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n- k}{k}.[/MATH]
Proof
[MATH]F_{0+1} = F_1 = 1 = \dbinom{0}{0} = \dbinom{0 - 0}{0} = \sum_{k=0}^0 \dbinom{0 - k}{k}.[/MATH]
[MATH]F_{0 + 2} = F_2 = F_0 + F_1 = 0 + 1 = 1 + 0.[/MATH]
[MATH]\therefore F_{0+2} = \dbinom{1}{0} + 0 = \dbinom{1 - 0}{0} + \dbinom{1 - 1}{1} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k}.[/MATH]
[MATH]\therefore \exists \text { a non-empty set } \mathbb J \text { such that any } j \in \mathbb J \implies [/MATH]
[MATH]j \in \mathbb N_0, \ F_{j+1} = \sum_{k=0}^j \dbinom{j - k}{k}, \text { and } F_{j+2} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k}.[/MATH]
[MATH]\text {For induction, we must show first that } F_{(j+1)+1} = \sum_{k=0}^{j+1} \dbinom{(j + 1) - k}{k}.[/MATH]
[MATH]F_{(j+1)+1} = F_{j+2} = \sum_{k=0}^{j+1} \dbinom{j + 1 - k}{k} = \sum_{k=0}^{j+1} \dbinom{(j + 1) - k}{k}.[/MATH]
[MATH]\text {That now done, we must next show that } F_{(j+1)+2} = \sum_{k=0}^{(j+1)+1} \dbinom{(j + 1) + 1 - k}{k}.[/MATH]
[MATH](j + 1) + 2 = j + 3 \ge 2 \ \because \ j \in \mathbb N_0.[/MATH]
[MATH]\therefore F_{(j+1)+2} = F_{j+1} + F_{(j+1)+1} = F_{j+1} + F_{j+2} \implies[/MATH]
[MATH]F_{(j+1)+2} = \left ( \sum_{k=0}^j \dbinom{j - k}{k} \right ) + \left ( \sum_{k=0}^{j+1} \dbinom{j +1 - k}{k} \right ) \implies[/MATH]
[MATH]F_{(j+1)+2} = \sum_{k=0}^{j+2} \dbinom{j + 2 - k}{k} \text { by Lemma II.}[/MATH]
[MATH]\therefore F_{(j+1)+2} = \sum_{k=0}^{(j+1) + } \dbinom{(j + 1) + 1 - k}{k}[/MATH]
[MATH]\text {By induction, } n \in \mathbb N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n - k}{k} \text { and } F_{n+2} = \sum_{k=0}^{n+1} \dbinom{n + 1 - k}{k}.[/MATH]
[MATH]\therefore n \in \mathbb N_0 \implies F_{n+1} = \sum_{k=0}^n \dbinom{n - k}{k} \text { Q. E. D}[/MATH]
D
Deleted member 4993
Guest
Subhotosh
Thank you.
If I knew any advanced mathematics, it might make me speedier. As it was, I am guessing that this problem was posed in a class that had available some general purpose theorems that I either never knew or have long forgotten. I used a spreadsheet to indicate whether the theorem was true (I have wasted a lot of time trying to prove things that turned out to be false). The spreadsheet then gave me clues on how to proceed with a formal proof. Then came reducing it to just two lemmas. At one point I needed six. And finally putting it all into LaTeX, which was tedious in the extreme.
Thank you.
If I knew any advanced mathematics, it might make me speedier. As it was, I am guessing that this problem was posed in a class that had available some general purpose theorems that I either never knew or have long forgotten. I used a spreadsheet to indicate whether the theorem was true (I have wasted a lot of time trying to prove things that turned out to be false). The spreadsheet then gave me clues on how to proceed with a formal proof. Then came reducing it to just two lemmas. At one point I needed six. And finally putting it all into LaTeX, which was tedious in the extreme.
D
Deleted member 4993
Guest
An excellent road-map for successful problem-solving-process.