[Date Index] [Thread Index] [Author Index]

Re: sum of recursive fn: solving for n

• To: mathgroup at smc.vnet.net
• Subject: [mg22169] Re: sum of recursive fn: solving for n
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Thu, 17 Feb 2000 01:23:58 -0500 (EST)
• References: <888afd$c7p@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"fiona" <reply at newsgroup.please> wrote in message
news:888afd$c7p at smc.vnet.net...
>
> what am i doing wrong here?
>
> f[x_] := (f[x-1])*2
> f[1] =2
> Solve[Sum[f[x], {x, 1,n}] ==62, n]
>
> tia,
> fiona
>
Fiona:

Your doing nothing wrong, its just the way Mathematica works.
First,  if we try to evaluate f[x], when x is not a posive integer, then we
never reach f[2] and we go on until stopped by the recursion linit.

f[x]

$RecursionLimit::"reclim": "Recursion depth of \!\(256\) exceeded."

5789604461865809771178549250434395392663499233282028201972879200395656481996
8 \
Hold[f[(-254 + x) - 1]]

Now, why do we get

Sum[f[x], {x, 1, n}]

$RecursionLimit::"reclim": "Recursion depth of \!\(256\) exceeded."
...........

    \!\(\[Sum]\+\(x = 1\)\%n f[x]\)

This happens since {x,1,n} does not allow Mathematica to construct an
explicit sequence of values (not knowing what n is).
In  these circumstances it evaluates f[x] , to val say, and tries to find a
formula for Sum[val,{x,1,n}]
 So it tries find a formula for

Sum[578960446186580977117854925043439539266349923328202820197287920039565648
19\
968 Hold[f[(-254 + x) - 1]], {x, 1, n}]

It fails to find one, and so returns the original input.
Finally , Solve can't deal with this.




Her are three little experiments

1)

i = 1; While[Sum[f[x], {x, 1, i}] < 62, ++i]; i

5

Sum[f[x], {x, 1, 5}]

62

Clear[f, i]

2)

We can see that f[n] = 2^n (and we could prove it by induction)
Or we could use

<< DiscreteMath`RSolve`

RSolve[{f[i] == 2 f[i - 1], f[1] == 2}, f[i], i]

\!\({{f[i] -> 2\^i}}\)

Sum[2^y, {y, 1, n}] // InputForm

2*(-1 + 2^n)

And then use Solve

Solve[% == 62]

Solve::"ifun": "Inverse functions are being used by \!\(Solve\), so some \
solutions may not be found."

{{n -> 5}}

Clear[f, i]

3) Use

RSolve[{S[n + 1] == S[n] + f[n + 1], S[1] == f[1], f[n] == 2 f[n - 1],
      f[1] == 2}, {f[n], S[n]}, n] // InputForm

{{f[n] -> 2^n, S[n] -> 2*(-1 + 2^n)}}

Solve[(S[n] /. %) == {62}, n]

Solve::"ifun": "Inverse functions are being used by \!\(Solve\), so some \
solutions may not be found."

{{n -> 5}}


Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565