How to proof; a sumformula

[Vince00]

Homework Statement

Proof that $$\sum a, m=0,$$ (a-m)! / m!(a-2m)! = the fibonacci sequence.

Homework Equations

Fibonacci: 1, 1, 2, 3, 5, ... (but I think everyone knows that one!)

The Attempt at a Solution

Let Xm = $$\suma m=0$$ (a-m)! / m!(a-2m)!
I think I better proof Xm+2 = Xm+1 + Xm (follows from the fibonacci), so I can conclude that Xm = Fm+1.
I think using induction is the best way to go: Prooving it for X0 and X1, maybe even X2.
My attempt:
$$\sum a+2, m=0,$$ (a+2-m)! / m!(a+2-2m)! = $$\sum a+1, m=0,$$ (a+1-m)! / m!(a+1-2m)! + $$\sum a, m=0,$$ (a-m)! / m!(a-2m)!
=$$\sum a+1, m=0,$$ (a+1-m)! / m!(a+1-2m)! + $$\sum a+1, m=1,$$ (a-m-1)! / (m-1)!(a-m-1-m+1)! ... but I think I am making big mistakes here, because whatever I do, I get stuck.
I just don't see it!

Vince, freshmen physics, sorry but I don't know how to use the symbols and stuff!

 

[n!kofeyn]

It's difficult to read what you have written. Try editing it by using the proper LaTeX. Just click on my output below to see the way to do it.
$$\sum_{n=0}^\infty a_n$$ for sums and subscripts
$$\frac{(a-m)!}{m!(a-2m)!}$$ for fractions
Also, what is Xm?

 

[Architeuthis Dux]

Hello Vince,

Thank you for sharing your attempt at solving this problem. I would approach this proof using mathematical induction, just like you suggested. Here's how I would go about it:

First, let's define the Fibonacci sequence as F(n), where n is the position in the sequence. So, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, and so on. We want to prove that the given sum formula is equal to the Fibonacci sequence, or in other words, Xm = Fm+1.

Step 1: Base case
To use induction, we need to prove that the formula holds true for the first few cases. In this case, we can start with Xm = X0, which is equal to 1 (since m = 0). And F1 = 1, so our formula holds true for the first case.

Step 2: Inductive hypothesis
Assuming that Xm = Fm+1 for some arbitrary value of m, we need to prove that Xm+1 = Fm+2.

Step 3: Proving the inductive step
Let's start by expanding Xm+1 using the given sum formula:
Xm+1 = \sum a, m+1 = 0, (a-(m+1))! / (m+1)!(a-2(m+1))!
= \sum a, m+1 = 0, (a-m-1)! / (m+1)!(a-2m-2)!
= \sum a, m+1 = 0, (a-m-1)! / m!(a-2m-2)! * (a-m-1)/(a-2m-2)

Now, using our inductive hypothesis, Xm = Fm+1, we can rewrite the first term as Fm+1. And we know that the Fibonacci sequence follows the recursive formula F(n+1) = F(n) + F(n-1), which can also be written as F(n) = F(n+1) - F(n-1). Using this, we can rewrite the second term as Fm.

So, Xm+1 = Fm+1 * (a-m-1)/(a-2m-2) + Fm. Now, let's simplify this further:
Xm+