Show it without using induction?

[3.14lwy]

how to show this:

if f(x) = 2x/(2x-1)

then show f(n) + f(n)f(n-1) + f(n)f(n-1)f(n-2) + ... + f(n)f(n-1)f(n-2)...f(1) = 2n .


I have tried to use induction , and I can show it.
but , I can't show it without using induction.


can anyone tell how to show it without using induction?

thank you !

 

[matt grime]

let S(n) be the sum you want.

Can you relate S(n) to S(n-1) algebraically? Hint, does the LHS of your equation have anything common to every term?

 

[HallsofIvy]

Do you see what happens when you write out a few terms of the products?

f(1)f(2)= \frac{2}{1}\frac{4}{3}= \frac{(2)(4)}{(1){3}}
f(1)f(2)f(3)= \frac{2}{1}\frac{4}{3}\frac{6}{5}= \frac{(2)(4)(6)}{(1)(3)(5)
and so on. You get a fraction with something "like" a factorial in both numerator and denominator except that the numerator has only even numbers and the denominator only odd numbers.

(2)(4)(6)...(2n)= (2)(1)(2)(2)(2)(3)...(2)(n)= 2ⁿ n!
and (1)(3)(5)...(2n+1)= ((1)(2)(3)(4)(5)...(2n)(2n+1))/(2)(4)...(2n))
= (2n+1)!/(2ⁿn!)
Does that give you any ideas?

 

[3.14lwy]

let S(n) be the sum you want.

Can you relate S(n) to S(n-1) algebraically? Hint, does the LHS of your equation have anything common to every term?

I find S(n) = f(n)*S(n-1)

and f(n) = (2^2n)(n!)/(2n+1)!

then , S(n) = product of (2^2r)(r!)/(2r+1)! from r = 1 to n

am I right ?

however i still don't know how to do?

 

[matt grime]

I find S(n) = f(n)*S(n-1)
am I right?

No, you're not right.

 

[3.14lwy]

No, you're not right.

Oh!

it should be S(n) = f(n)[1 + S(n-1)]

but still don't know

if it is in this from:

X(n) = aX(n-1) + b

i can find X(n) in term of a , b and X(1) ,


but now the a and the b is changing........

 

[matt grime]

You've found a first order difference equation. As with differential equations you guess a solution by inspection based upon f(n).

 

[3.14lwy]

You've found a first order difference equation. As with differential equations you guess a solution by inspection based upon f(n).

S(n) = f(n)[1 + S(n-1)]

S(n) - S(n-1) = f(n)[1 + S(n-1)] - S(n-1)
= f(n) + [f(n) - 1]S(n-1)

____________________________________________________

S(1) = 2/1 = 2

S(2) = 4/3 + 8/3 = 12/3 = 4

S(3) = 6/5 + (6*4)/(5*3) + (6*4*2)/(5*3*1)
= 2*3/5 + 2*4/5 + 2*4*2/5
= 2[3/5 + 3*(4/5)]
= 2*3*(5/5) = 6

S(4)
...
...
...
..
.

S(2) - S(1) = 2......
......


I really cannot find the solution

 

[matt grime]

You're given 2n, and asked to *show* it is the solution, so it is perfectly acceptable to check it satisfies the recurrence relation by simple substitution.

And:

S(n) = \frac{2n(1+S(n-1))}{2n-1}

it is clear what kind of answer you should guess from looking at that ie that 2n is what you want since 2n-1 = 2(n-1)+1