Could someone help me with these questions please.
I really don't know where to start.
2) T(n)=2T(n/3)+n log n
I suspect that these are difference equations.
Take the first one for example,
That would imply that and so on.
The object of the exercise is to find an expression for
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 for some constants and substitute into the difference equation, treating it as an identity.
Solve, and you should find that
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.
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
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 we 'guess' that the solution is of the form where are constants, to be calculated.
Substitution into the equation gets us
and on rearranging,
This is to be considered as an identity, that is, it has to be true for all values of
That implies that (the part without the in it must equal zero).
In answer to your other question, I struggle with one quote let alone two or more.