Dsicrete Mathematics - Revision - 25th June - ROSEN - Discrete Math & its Applications

DM-25Jun

Discrete Math - solutions - Exercise 5.4
Page no 370 

Q7. Give a recursive definition and  algorithm for computing nx whenever n is a positive integer and x is an integer, using just addition.
P(0): x(0) = 0
Nx = x+(n-1)x

Procedure mult (n: positive integer, x: integer)
if n=1 then mult(n,x):=x
else mult(n,x):=x+mult(n-1,x)

Q9 Give a recursive definition and  algorithm for finding the sum of the first n odd positive integers.

P(0)= 0
Sum(n) = sum(n-1) + (2n-1)

Procedure sum_of_odds (n: positive integer)
if n=1 then sum_of_odds (n):=1
else sum_of_odds (n):=sum_of_odds (n-1)+2n-1


Q23. - Devise a recursive algorithm for computing n 2 , where n is a nonnegative integer
using the fact that (n + 1) 2 = n 2 + 2n + 1.
Answer:
int f( int n )
{
if ( n == 0 )
return 0;
else
return f( n - 1 ) + 2*n - 1;
}

Q32. Devise a recursive algorithm to find the nth term of the sequence defined by
a0 = 1, a1 = 2, a2 = 3 and an = an-1 + an-2 + an-3, for n = 3, 4, 5, . . .

SOLUTION:		int function Sequence ( n: non-negative integer ) 
    { 
        int k ; 

        if ( n < 3 ) 
            { 
                k = n + 1 ; 
            } 
        else 
            { 
                k = Sequence ( n - 1 ) + Sequence ( n - 2 ) + Sequence ( n - 3 ) ; 
            } 

        return ( k ) ; 
    }