Re: Recursive Proofs...
- To: mathgroup at smc.vnet.net
- Subject: [mg29965] Re: Recursive Proofs...
- From: Ignacio Rodriguez <ignacio at sgirmn.pluri.ucm.es>
- Date: Fri, 20 Jul 2001 03:28:29 -0400 (EDT)
- Organization: UCM
- References: <9j0hdr$fje$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Mr Trichard,
It is possible to use mathematical induction, but please be aware that
Mathematica will not do it by itself.
For example, imagine we define f as
f[0]=0;
f[n_]:=r f[n-1]+a;
and we want to prove that f[n] equals a Sum[r^i,{i,0,n-1}]. We cannot use just
Simplify[f[n]==a Sum[r^i,{i,0,n-1}] as this would lead to an infinite
recursion. However, we can try induction like this
Simplify[(0==a Sum[r^i,{i,0,-1}])&&(r a Sum[r^i,{i,0,n-1}]+a==a
Sum[r^i,{i,0,n}])]
In your case, if you have a 2d recursion it may be a bit more difficult, but
the procedure is esencially the same.
Louis Trichard wrote:
> Dear All,
>
> I have a complicated 2d recursion in which I'd like to prove that the
> r(i,i) = a^i. (i.e. something simple) by induction. I've left out the
> definition of the recursive function, since it is not necessary.
>
> I can use mathematica to show this simple expression for i = 1..100 or
> more, i.e. Simplify[r[10,10]] = a^10, but this is no proof.
>
> I would like some general advice on:
> 1/ How could one use mathematica to help prove such recursive
> expressions by induction (or other methods) for general i, i.e. I know one
> cannot use Simplify[r[i,i]], since this would give an infinite recursion
> depth error.
>
> Thanks for all your help,
>
> Louis Trichard
--
Ignacio Rodriguez Ramirez de Arellano
Unidad de RMN
Universidad Complutense
Paseo Juan XXIII, 1
Madrid 28040, Spain
Tel. 34-91-394-3288
Fax 34-91-394-3245
e-mail: ignacio at sgirmn.pluri.ucm.es