0
$\begingroup$

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.

  • 1
    Why don't you post what you are doing here instead of linking to a google doc?2011-10-10
  • 0
    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.2011-10-10
  • 0
    Also the PDF I've linked is colourful and pretty.2011-10-10
  • 3
    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.2011-10-10
  • 2
    @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.2011-10-10
  • 0
    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.2011-10-10
  • 0
    @J.M.: Also known as ["rubber duck debugging"](http://en.wikipedia.org/wiki/Rubber_duck_debugging) (as [here](http://lists.ethernal.org/oldarchives/cantlug-0211/msg00174.html)).2011-10-14
  • 0
    @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.2011-10-14

3 Answers 3

0

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.

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.

  • 0
    I had noticed this but I'm not entirely sure how to use this knowledge.2011-10-10
  • 0
    Unfold and Sum is backward substitution elsewhere (such as described on [this page](http://homepages.ius.edu/rwisman/C455/html/notes/chapter4/Recurrence%20Tutorial.htm))2011-10-10
  • 0
    For example, $v(1) = 6$ and $v(n) = f(2n) = v(n - 1) + 3(2n)$.2011-10-10
  • 0
    I gathered, however I'm not entirely sure whether I will be allowed all of the marks by doing that.2011-10-10
0

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

  • 0
    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?2011-10-10