Monday, 8 April 2019

10:44 AM

For  consider the set of all -digit numbers formed by the digits 1,2,3,4,5,6,7.

Let  be the set of such numbers whose sum of digits is odd

Let  be the set of numbers whose sum of digits is even

 

1. Write  in terms of

 

2. Obtain a recurrence relation for

Since , and …

An n-digit number which sums to odd can be formed by

 

(appending an even digit after an n-1 digit which sums to odd

 

Appending an odd digit after an n-1 digit which sums to even

 

Thus,

 

 (The numbers 1,3,5,7)

This is an example of a non-homogeneous recurrence