Discrete Mathematics Test 5

Concept:

For a sequence {a₀, a₁, a₂, a₃,………….,a_n} of real numbers, the generating function will be defined as :

F(x) = a₀+ a₁x + a₂x² + a₃x³ + ………+ a_nxⁿ

Then for this we take the binomial expansion, such as this generating cuntion is binomial expansion of (1 + x)ⁿ.

Explanation:

Here , sequence is : {1,1,3,1,1,1,1……………}

F(x) = 1 + x + 3x² + x³ + x⁴ + ………+ xⁿ

= (1 + x + x² + x³ + ……..) + 2x²

= (1 - x)^-1 + 2x²                        

We can also write it as :

We can construct a bit string of length eight that begins with a 1 in 2⁷ =128 ways.

Similarly, we can construct a bit string of length eight ending with the two bits 00, in 2⁶ =64 ways. 

Some of the ways to construct a bit string of length eight starting with a 1 are the same as the ways to construct a bit string of length eight that ends with the two bits 00. There are 2⁵ =32 ways to construct such a string.

The number of ways to construct a bit string of length eight that begins with a 1 ort hat ends with 00 = 128+64−32=160. 

As we know that number of ways of selecting r things out of n is equal to ⁿC_r.

And   ⁿC_r  =  \(\frac{{n!}}{{r! \times (n - r)!}}\)

We may have (3 men and 2 women) or (4 men and 1 women) or (5 men only)

∴ required number of ways = (⁷C₃ × ⁶C₂) + (⁷C₄ + ⁶C₁) + ⁷C₅

= {(7 × 6 × 5)/(3 × 2 × 1) × (6 × 5)/(2 × 1)} + (⁷C₄ + ⁶C₁) + ⁷C₅

= 525 + {(7 × 6 × 5)/(3 × 2 × 1)× 6} + (7 × 6)/(2 × 1)

= 525 + 210 + 21 = 756

Although base condition is not mentioned for tower of Hanoi when number disc is 0, that is, n = 0

number of moves needed is 0.

T(0) = 0 (base condition for Tower of Hanoi)

T(1) = 2 × T(0) + 1 = 0 + 1 = 1

T(2) = 2 × T(1) + 1 = 2 + 1 = 3

T(3) = 2 × T(2) + 1 = 6 + 1 = 7

T(4) = 2 × T(3) + 1 = 14 + 1 = 15

T(5) = 2 × T(4) + 1 = 30 + 1 = 31

T(6) = 2 × T(5) + 1 = 62 + 1 = 63

T(7) = 2 × T(6) + 1 = 126 + 1 = 127

Tips and Tricks:

Number of moves required for n disc in a Tower of Hanoi is 2ⁿ – 1 = 2⁷ – 1 = 127.

Formula:

\({\left( {1 - ax} \right)^{ - k}} = \;\mathop \sum \limits_{n = 0}^\infty C_n^{n - 1 + k} \times {x^n}\)

Explanation:

Given function is:

= (x³ + x⁴ + x⁵ + …………)⁵

We can write it as: x¹⁵(1 + x² + x³ + ……….)⁵

= x¹⁵ (1- x)^-5

\( = {x^{15}}\mathop \sum \limits_{n = 0}^\infty C_n^{n + 4} \times {x^n}\)

Consider n = 5

\( = {x^{20}}\mathop \sum \limits_{n = 0}^\infty C_5^{5 + 4}\)

T (n) = 10 T(n-1) – 25 T(n-2)

We can write it as :

T(n) – 10 T(n-1) + 25 T(n-2) = 0

Then in polynomial form, it can be represented as :

x² – 10x + 5 = 0

(x - 5)² = 0

Then the characteristic equation will be :

T(n ) = C₁5ⁿ + C₂.n.5ⁿ

T(0) = T(1) = 5

So, T(0) = C₁5⁰ + C₂.0.5⁰

5 = C₁

Now, T(1) = C₁ 5¹ + C₂1.5¹

5 = 5C₁+ 5C₂

i.e. C₁ + C₂ = 1

C₂ = -4

So, T(n) = 5.5ⁿ + (-4)n.5ⁿ

a_n = a_{n – 1} + 6n² + 2n

= a_n-2 + 6(n-1)² + 2(n-1) + 6n² + 2n

\(\begin{array}{l} \equiv {a_1} + 6\mathop \sum \limits_{i = 2}^n {i^2} + 2\mathop \sum \limits_{i = 2}^n i\\ \equiv 8 + 6\left[ {\frac{{n\left( {n + 1} \right)\left( {2n + 1} \right)}}{6} - 1} \right] + 2\left[ {\frac{{n\left( {n + 1} \right)}}{2} - 1} \right]\\ \equiv 8 + 6\left[ {\frac{{n\left( {n + 1} \right)\left( {2n + 1} \right) - 6}}{6}} \right] + 2\left[ {\frac{{n\left( {n + 1} \right) - 2}}{2}} \right] \end{array}\)

≡ 8 + n (n+1) (2n+1) – 6 + n(n+1) – 2

a_n = n(n + 1) (2n + 2)

a_aa = k × 10⁴

Also,

a_aa = 99 (99 + 1) (198 + 2)

= 99 × 10² × 2 × 10²

= 198 × 10⁴

\({a_n} = 5n + 2\)

a₀ = 2,a1 = 7, a2 =12, a3 = 17

Sequence: 2, 7, 12, 17 …

\(G\left( x \right) = 2 + 7x + 12{x^2} + 17{x^3} + \; \ldots\)    (1)

\(xG\left( x \right) = 2x + 7{x^2} + 12{x^3} + \; \ldots \;\)    (2)

Subtracting (1) and (2)

\(\left( {1\; - x} \right)G\left( x \right) = 2 + 5x + 5{x^2} + 5{x^3} + \; \ldots \)

\(\left( {1 - x} \right)\;G\left( x \right) = \;\;2 + 5x\left( {1\; + x\; + {x^2} + \; \ldots } \right)\)

\(\left( {1 - x} \right)\;G\left( x \right) = 2 + \frac{{5x}}{{1 - x}}\)

\(\left( {1 - x} \right)\;G\left( x \right) = \frac{{3x + 2}}{{1 - x}}\)

\(\therefore \;G\left( x \right) = \frac{{3x + 2}}{{{{\left( {1 - x} \right)}^2}}}\)

OR

\(\left( {1 - x} \right)\;G\left( x \right) = 2 + \frac{{5x}}{{1 - x}}\)\(\)

\(\;G\left( x \right) = \frac{2}{1-x} + \frac{5x}{(1-x)^2}\)

Characteristic equation of \({a_n} = 5{a_n}_{ - 1} - \;6{a_n}_{ - 2}\) is

\({r^2} - 5r + 6 = 0\)

\(\left( {r - 3} \right)\left( {r - 2} \right) = 0\)

∴ \(r = 3\;or\;r = 2\)

∴ \({r_1} = 3,\;{r_2} = 2\)

\({a_n} = {\alpha _1} \times {\left( r1 \right)^n} + {a_2} \times {\left( r2 \right)^n}\)

put \({a_0}\) = 1

\({a_n} = {\alpha _1} \times {\left( 2 \right)^n} + {a_2} \times {\left( 3 \right)^n}\)

\({a_0} = {\alpha _1} + {a_2} = 1\)        (I)

\(({\alpha _1} + {\alpha _2} + {r_1} + {r_{2\;}}) = 1 + 2 + 3 = {\rm{ }}6\)