## FY. Weights in a Row

What can you say about a sequence if you know that each term is a weighted average of the terms to either side?

For example, in the sequence 1, 2, 4, 8, 16, … each term is exactly 2/3rds of the previous term, plus 1/3rd of the following term. What *other* sequences have exactly that property?

For a given value p, what sequences s_{1}, s_{2}, s_{3}, … s_{n} have the property that each s_{k} = p s_{(k-1)} + (1-p) s_{(k+1)} ? Does knowing s_{1} also fix the remaining terms?

Amusingly, this actually will help with last weeks puzzle!

## Steven H. Noble said,

July 2, 2009 at 6:56 pm

I’ll be interested to see if you use this question as a springboard to talk about the properties of linear recurrences.

## Sam Martin said,

July 3, 2009 at 11:32 am

Urm. Not to be picky or anything, but those weights dont’ appear to match that sequence? Perhaps you mean 2x previous?

Or have my brains completely fallen out? I suspect I’m missing something…

## Sam Martin said,

July 3, 2009 at 11:33 am

btw – it’s a cracking job you guys do. Keep it up!

## strauss said,

July 6, 2009 at 4:20 pm

I think we have the weights right:

4 = 2/3 * 2 + 1/3 * 8

8 = 2/3 * 4 + 1/3 * 16

I think we should talk about linear recurrences! One of those things we just need to say something about! This example isn’t in just that form, but as Steven Noble probably spotted, it can be (should be?) thought of in that way.

## Sam Martin said,

July 7, 2009 at 6:11 am

Doh! Comical and blindingly obvious handwriting fail. Thanks!

## Brian said,

July 21, 2009 at 12:38 am

Ok after some thought, I found some methods for figuring this out.

Your sequence is powers of two, where the nth term is 2^n. I postulate here that the relationship described above is related to the exponetial curve. So I focused my exploration there thinking maybe this would apply to other exponential functions.

So first, I looked at the simplest one (this will be tricky to write without super/subcripts):

kx^0, kx^1, kx^2, … kx^n

where k is a constant coefficient and x raised to the nth power for each term. Applying the 1/3 & 2/3 condition, we get the following:

kx^n = (2/3)kx^(n-1) + (1/3)kx^(n+1)

Settles down to…

3kx = 2k + kx^2

k(x-1)(x-2) = 0

x = 1 or 2

Which leaves us with either all terms are equal (k) or x=2 (our original sequence). Both of these solutions work.

Next, I looked at the inverse to see if I could get any alternate variations

k, kx^-1, kx^-2, kx^-3, … kx^-n

Does this work? Let’s work it thorugh. First, the initial condition:

x^-n = (2/3)kx^1-n + (1/3)kx^(1+n)

Settles down to …

3kx = 2kx^2 +1k

k(1-x)(1-2x) = 0

x = -1 or -2.

x = -1 was already proved in the last problem, but just in case you didn’t get it:

sequence: k, k, k, k, …. k

k/3 + 2k/3 = k

Now let’s look at -2

k, k/2, k/-3, k/4, k/-5…

That doesn’t work because if x(n) is positive, x(n-1) and x(n+1) are both going to be negative.