# Show it without using induction?

1. Oct 18, 2004

### 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 !

2. Oct 18, 2004

### 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?

3. Oct 18, 2004

### 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)= 2n n!
and (1)(3)(5)...(2n+1)= ((1)(2)(3)(4)(5)...(2n)(2n+1))/(2)(4)...(2n))
= (2n+1)!/(2nn!)
Does that give you any ideas?

4. Oct 18, 2004

### 3.14lwy

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?

5. Oct 18, 2004

### matt grime

No, you're not right.

6. Oct 19, 2004

### 3.14lwy

Oh! :tongue:

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..................................

7. Oct 19, 2004

### matt grime

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

8. Oct 20, 2004

### 3.14lwy

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 realy cannot find the solution

Last edited: Oct 20, 2004
9. Oct 20, 2004

### 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

Last edited: Oct 20, 2004