Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
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. –  Ross Millikan Oct 10 '11 at 14:31
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. –  J. M. Oct 10 '11 at 14:33
show 3 more comments

3 Answers 3

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment
up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.