[seqfan] Re: linear recurrence multiples

[M. F. Hasler]

On Sun, Jul 21, 2019, 06:59 Dale Gerdemann  wrote:
> I experimented with finding simular formulae for other recurrences, i.e.

> for other values of b and  c.  The easiest way to do this is to pick a
> large value for  n, such as n=100. Then find a greedy sum for m*a(100) such
> as 2*a(100) = a(101) + a(98). Then generalize this to 2*a(n) = a(n+1) +
> a(n-2). Finally, to be sure that the generalized formulae is correct, it
> needs to be checked with some values other than  n=100.


I don't agree: a check isn't a proof (*), but it is easy to prove such
formulae rigorously by using the explicit expression for a(n).
(Google "second order linear recurrent sequence with constant coefficients"
to get all details.)

(* it may be sufficient to make  n "linearly independent" checks if you
test for an n dimensional subspace (loosely speaking), yet you have to
prove that you are in that setting and in particular that you made at least
n  "independent" checks)

Now my experimentation seems to show that this method yields valid formulae
> for recurrences defined with  b <= c, but  the generalized formulae are
> never valid when c > b. So what is going on here?
>

Could it be that this distinction is rather based on the sign of the
discriminant b²–4c ? The general theory explains the fundamental solutions
in the respective cases, which could in turn explain why & when a given
formula works (or not).


El El dom, 21 jul 2019 a las 0:32, Fred Lunnon <fred.lunnon at gmail.com>
> escribió:
>
> >   I'm afraid it is unclear to me what is meant by "formula" in this
> > context.
>

Same for me.
But maybe Ehren's earlier reply already settles the question.

>
A015518. For A007482, it seems to be possible
> > to
> > > find formulae for m*a(n) for any m. For example, if m=4, we have
> 4*a(n) =
> > > a(n+1)+a(n-1)+2*a(n-2). For A015518,  however, it seems that no such
> > > formulae can be found. It appears that such formulae can be found just
> in
> > > case b >= c.
>

IMHO a formula "of that type" (to be made precise) should always exist.
(See Ehren's reply for the cited case.)

- Maximilian