Combinatorics Question Help Please Prow the following identi

Combinatorics Question Help Please!!:

Prow the following identity. (n 0)F_0 +(n 1)F_1+(n 2)F_2+...+(n n)F_n=F_2n We prove both by simultaneous induction. (n 0) F_0 + (n 1) F_1 + (n 2) F2 + ... + (n n) F_n = F_2n (3.1) (n 0) F_1 + (n 1) F_2 + (n 2) F3 + ... + (n n) F_n+1 = F_2n+1 (3.2) Prove 3.3 for the parameter n, using the identities 3.3 and 3.4 for the cases with parameter (n - 1). Then show that the inductive hypotheses for 3.3 and 3.4 (i.e. with parameter (n - 1)) implies 3.4 for parameter n by induction. For this one. we also need to use the Fibonacci recurrence.

Solution

for base case this is valid since

nc0 Fo = Fo and F2n = Fo wwhen n=0 so for base case it is proved

let us suppose it is true for n = n

i.e . nc0 Fo + .....................+ncnFn = F2n is true

we then try to prove for n = n+1

now nc0 Fo + .....................+ncnFn = F2n

and F2n +ncnFn+1 = F2n +Fn+1 = F2n+1 by the help of Fibonacci recurrence i.e .Fn-1 +Fn = Fn+1