# T(n) questions

• Feb 24th 2014, 04:51 PM
Melody2
T(n) questions
Could someone help me with these questions please.
I really don't know where to start.
Thank you.

1) T(n)=7T(n-4)+n

2) T(n)=2T(n/3)+n log n

• Feb 24th 2014, 07:19 PM
Prove It
Re: T(n) questions
There are not any questions posted here, only equations. What are you trying to do with these equations?
• Feb 24th 2014, 07:50 PM
Melody2
Re: T(n) questions
Thank you Prove It.
I really have no idea. I was actually wondering if i even had a question. Thanks for clearing that up.
Maybe they were intended as simultaneous equations. I really don't know.
Regards,
Melody.
• Feb 25th 2014, 03:35 AM
BobP
Re: T(n) questions
Hi Melody

I suspect that these are difference equations.

Take the first one for example, $\displaystyle T(n)=7T(n-4)+n.$

That would imply that $\displaystyle T(4)=7T(0)+4, \quad T(5)=7T(1)+5, \quad T(6)=7T(2)+6$ and so on.

The object of the exercise is to find an expression for $\displaystyle T(n).$

The general solution of the equation is quite messy (and I would guess that it is not what is required), but the particular solution is relatively easy to find.

Assume that $\displaystyle T(n)=An + B$ for some constants $\displaystyle A \text{ and } B$ and substitute into the difference equation, treating it as an identity.

Solve, and you should find that $\displaystyle T(n)=-\frac{n}{6}-\frac{7}{9}=\text{ (for convenience )}-\frac{3n}{18}-\frac{14}{18}.$

So,

$\displaystyle T(0)=-14/18, \quad T(1)=-17/18, \quad T(2)=-20/18, \quad T(3)=-23/18,$

$\displaystyle T(4)=-26/18, \quad T(5)=-29/18, \quad T(6)=-32/18$

and so on.

Check to see that these satisfy the three example equations I gave earlier.

Try your luck with the second one, I've not attempted it yet.
• Feb 25th 2014, 05:37 PM
Melody2
Re: T(n) questions
Quote:

Originally Posted by BobP
Hi Melody

I suspect that these are difference equations.

Take the first one for example, $\displaystyle T(n)=7T(n-4)+n.$

That would imply that $\displaystyle T(4)=7T(0)+4, \quad T(5)=7T(1)+5, \quad T(6)=7T(2)+6$ and so on.

The object of the exercise is to find an expression for $\displaystyle T(n).$

The general solution of the equation is quite messy (and I would guess that it is not what is required), but the particular solution is relatively easy to find.

Assume that $\displaystyle T(n)=An + B$ for some constants $\displaystyle A \text{ and } B$ and substitute into the difference equation, treating it as an identity.

Why would i assume the above line and how would that lead to the below line? (Thinking)

Quote:

Originally Posted by BobP
Solve, and you should find that $\displaystyle T(n)=-\frac{n}{6}-\frac{7}{9}=\text{ (for convenience )}-\frac{3n}{18}-\frac{14}{18}.$

So,

$\displaystyle T(0)=-14/18, \quad T(1)=-17/18, \quad T(2)=-20/18, \quad T(3)=-23/18,$

$\displaystyle T(4)=-26/18, \quad T(5)=-29/18, \quad T(6)=-32/18$

and so on.

Check to see that these satisfy the three example equations I gave earlier.

Thanks BobP,
I have include a question inside - I can't get this multi quote thing to work. I separated the two bits myself.
Please can someone tell me what the trick is to using multi quote (Headbang)
• Feb 26th 2014, 01:17 AM
BobP
Re: T(n) questions
The method I used is known as a 'trial solution method', and it is just that. You try something, if it works fine, if not try something else. With practice it's usually possible to guess what the solution looks like.
Have you done any work on second order ODE's with constant coefficients ? That's where your most likely to come across it. It's a commonly taught method for finding the Particular Integral. The general solution of such an equation will consist of the Particular Integral plus a Complementary Function (which is the solution of the corresponding homogeneous equation and which will contain two arbitrary constants). It's pretty much the same for the difference equation we are discussing, its general solution consists of two parts, a Particular Solution (which is what I've found), plus the solution of the corresponding homogeneous equation, (which I haven't).

For the equation $\displaystyle T(n)=7T(n-4)+n,$ we 'guess' that the solution is of the form $\displaystyle T(n)=An+B$ where $\displaystyle A \text{ and } B$ are constants, to be calculated.

Substitution into the equation gets us $\displaystyle An+B=7\{A(n-4)+B\}+n,$

and on rearranging, $\displaystyle -6An+28A-6B=n.$

This is to be considered as an identity, that is, it has to be true for all values of $\displaystyle n.$

That implies that $\displaystyle A=-1/6 \text{ and }B=-7/9,$ (the part without the $\displaystyle n$ in it must equal zero).

In answer to your other question, I struggle with one quote let alone two or more.