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.

  • 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 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