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

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
Also the PDF I've linked is colourful and pretty. – KitB Oct 10 '11 at 14:29
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. Oct 10 '11 at 14:33

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.

-
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

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

-
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

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.

-