# recurrence and algorithm

• May 19th 2007, 02:01 AM
fortuna
recurrence and algorithm
Discrete maths
I have three questions which I have spent time trying to do since the begining of this week but not sure whether I am at the right track.
Would appreciated if you could help me. It has drive me crazy.
I have typed and attached the questions as attachment as I cannot type maths super or sub script on this email.

Help, it is driving me crazy!

Thanks

Fortuna:confused:
• May 19th 2007, 05:53 AM
Soroban
Hello, fortuna!

Here's #3 . . .

Quote:

3. Solve the recurrence relation: .an .= .10·an-1 - 25·an-2, .a0 = 2, a1 = 15.

Hint: If the characteristic equation factors to (t - r)²,
. . . . then the general solution is: .a
n .= .b·r^n + c·n·r^n
The characteristic equation is: .t^n .= .10·t^{n-1} - 25·t^{n-2}

. . Divide by t^
{n-2}: . .= .10t - 25 . . . . t² - 10t + 25 .= .0

. . Hence: .(t - 5)² .= .0

Then the general solution is: .a
n .= .b·5^n + c·n·5^n

Since a
0 = 2, we have: .b·5^0 + c·0·5^0 .= .2 . . . . b = 2

Since a
1 = 15 and b = 2, we have: .2·5 + c·1·5 .= .15 . . . . c = 1

Therefore, the general solution is: .a
n .= .2·5^n + n·5^n

• May 19th 2007, 07:04 AM
CaptainBlack
procedure SortBits(S,i,j) {

.. if (i==j)
.... return ..............
.. if (s(i) == 1){
.... swap(s(i), s(j))
.... SortBits(S,i,j-1)
.... }
.. else {
.... SortBits(S,i+1,j)
.. }
}

(a) If the length of the unsorted part of the sequence is 1 j=i+1 in the call
SortBits(S, i, j). So one of the lines SortBits(S,i,j-1), or SortBits(S,i+1,j)
is executed both of which do nothing and return, so b1 = 1.

(b) Entering the with j=i+n, SortBits is called with an unsorted length
of n-1, so:

b_{n} = 1 + b_{n-1}

(c) I'm not sure what solution method you are expected to use, but
the solution is b_n = n.

(d) b_{25} = 25.

RonL
• May 21st 2007, 09:29 AM
fortuna
Question one - Any chance of a solution
Captain Black

Is is possible still to get the workings and solution to question one.

Thanks.

Fortuna:confused:
• May 21st 2007, 02:32 PM
CaptainBlack
Quote:

Originally Posted by fortuna
Captain Black

Is is possible still to get the workings and solution to question one.

Thanks.

Fortuna:confused:

Unfortunatly I don't understand what the question is asking.

RonL