1. ## 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

2. Hello, fortuna!

Here's #3 . . .

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

3. 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

4. ## Question one - Any chance of a solution

Captain Black

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

Thanks.

Fortuna

5. Originally Posted by fortuna
Captain Black

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

Thanks.

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

RonL