In attempting a closed solution for a recurrence, what am I failing to do?

Question

I'm doing a coursework assignment and find myself rather stuck. I thought I understood back-substitution as a method for solving recurrences but am not finding my working to be getting me anywhere. My current question is just "What am I doing wrong in my working?". Here is my current working.

Thank you so much in advance.

The problem is $f(1)=2, f(2)=6, f(n)=f(n-2)+3n$

My working is:

$$f(n)=f(n-2)+3n$$ $$=f(n-4)+3(n-2)+3n=f(n-4)+6n-6$$ $$=f(n-6)+3(n-4)+6n-6=f(n-6)+9n-18$$ $$=f(n-8)+3(n-6)+9n-18=f(n-8)+12n-36$$ $$...=f(n-2k)+3kn-3k(k-1)$$

then put $k= {n-1 \over 2}$: $$f\left(n-2{n-1\over 2}\right)+3\left({n-1 \over 2}\right)n-3\left({n-1 \over 2}\right)\left({n-1 \over 2}-1\right)$$ $$=...={1 \over 4}\left(9n^2-18n+17\right)$$

But this does not check for $n=2$ or $n>3$

And yes, I have no choice but to use this method or similar to "guess" the form then prove it by induction.

Why don't you post what you are doing here instead of linking to a google doc? — André Caldas, Oct 10 '11 at 14:26
Because I've already written it all up once and it's nice and easy for me to just post that rather than learning the requisite syntax (LaTeX, I presume) then typing the whole thing in here. — KitB, Oct 10 '11 at 14:28
It would be better to type up your work with explanation in the question than link to a picture. I find putting in the explanation of what I was thinking often leads to finding the error. — Ross Millikan, Oct 10 '11 at 14:31
@Ross: Ah, "confessional debugging". Saved me more than once... Kit, Ross is right; often writing the steps again might lead you to see things you never saw previously. — J. M. ain't a mathematician, Oct 10 '11 at 14:33
Though I've written much the same working a few times now (you guys don't see the erased sections) I shall endeavour to write it up here. — KitB, Oct 10 '11 at 14:35
@Shree: Thanks for that. :) I picked the name I'm accustomed to from McConnell's wonderful Code Complete; now I have two names to pick from. — J. M. ain't a mathematician, Oct 14 '11 at 13:33

TonyK · Answer 1 · 2011-10-10T14:48:07.350

1

Notice that the sequence can be split into two sub-sequences, the odd-numbered elements and the even-numbered elements, defined independently of each other. So you can solve each sub-sequence separately, and re-combine them at the end.

Edited after comment: Define $u_n = f_{2n-1}$ and $v_n = f_{2n}$ , and take it from there. It's easy! But I don't know what "unfold-and-sum" is.

edited Oct 10 '11 at 14:48

answered Oct 10 '11 at 14:30

TonyK

64,559

I had noticed this but I'm not entirely sure how to use this knowledge. – KitB Oct 10 '11 at 14:31
Unfold and Sum is backward substitution elsewhere (such as described on this page) – KitB Oct 10 '11 at 15:11
For example, $v(1) = 6$ and $v(n) = f(2n) = v(n - 1) + 3(2n)$. – André Caldas Oct 10 '11 at 15:36
I gathered, however I'm not entirely sure whether I will be allowed all of the marks by doing that. – KitB Oct 10 '11 at 15:45

score 0 · Answer 2 · answered Oct 10 '11 at 14:33

0

It isn't finding the error, but defining $g(n)=f(n)-\frac{3n^2}{4}$ (chosen to eliminate the $3n$ term) helps.

answered Oct 10 '11 at 14:33

Ross Millikan

374,822

The question explicitly tells me to solve it using "unfold-and-sum" which I've discovered everyone except my lecturer calls "Backward Substitution". Would doing this affect this method? – KitB Oct 10 '11 at 14:36

score 0 · Accepted Answer · answered Oct 14 '11 at 13:19

In the step from $$f\left(n-2{n-1\over 2}\right)+3\left({n-1 \over 2}\right)n-3\left({n-1 \over 2}\right)\left({n-1 \over 2}-1\right)$$ $$=...={1 \over 4}\left(9n^2-18n+17\right)$$ In my working I made a sign error, this actually should read $$f\left(n-2{n-1\over 2}\right)+3\left({n-1 \over 2}\right)n-3\left({n-1 \over 2}\right)\left({n-1 \over 2}-1\right)$$ $$=...={1 \over 4}\left(3n^2+6n-1\right)$$

which works for the odd subsequence. Following some more working the even sequence comes to be $$={1 \over 4}\left(3n^2+6n\right)$$ (Here I also made a sign error)

and combining them gives $${1 \over 8}\left(6n^2+12n-1+(-1)^n\right)$$ Which is exactly what Wolfram|Alpha told me it would be.

Thanks for the help.

In attempting a closed solution for a recurrence, what am I failing to do?

3 Answers3