Computational Mathematics Previous year solutions

2020

5(a) Prove that for a random variable x, Var(X)=E(X2)-µ2 where µ is the mean value of the
population

Ans) We are asked to prove that the variance of a random variable X is given by:
Var(X)=E(X2)−μ2 where μ=E(X) is the mean of the population.
The variance of a random variable X is defined as the expected value of the squared deviation from
the mean:
Var(X)=E[(X−μ)2] where μ=E(X).
Expanding the square inside the expectation:
(X−μ)2=X2−2μX+μ2
Taking the expectation of both sides:
E[(X−μ)2]=E[X2−2μX+μ2]
The expectation operator is linear, so using linearity of expectation, we get:
E[X2−2μX+μ2]=E(X2)−2μE(X)+E(μ2)
But μ=E(X), so E(X)=μ and μ2 is a constant, so E(μ2)=μ2
By substitution,
E(X2)−2μ⋅μ+μ2=E(X2)−2μ2+μ2=E(X2)−μ2
Therefore, Var(X)=E[(X−μ)2]=E(X2)−μ2 (Hence Proved)

5(c) Find the generating function for the finite sequence 1,4,16,64,256
Ans) We are given the finite sequence:
1,4,16,64,256
Let's denote this sequence as a0, a1, a2, a3, a4, where:
a0=1, a1=4, a2=16, a3=64, a4=256
Expressing each term as a power of 4:
1=40
4=41
16=42
64=43 [43=4×4×4=64 which is true]
256=44 [44=4x4x4x4=256 which is true]
So, the general term is:
ak=4k for k=0,1,2,3,4
The generating function for a finite sequence a0, a1, …, an is defined as:
𝑛

𝐺(𝑥) = ∑ 𝑎𝑘 𝑥 𝑘
𝑘=0
In this case, n=4, and ak=4k, so:
4 4

𝐺(𝑥) = ∑(4 )𝑥 = ∑(4𝑥)𝑘

𝑘 𝑘

𝑘=0 𝑘=0

This is a finite geometric series with first term 1 and common ratio r=4x.
Using the Geometric Series Formula
The sum of a finite geometric series is:
𝑛
𝑟 𝑛+1 − 1
∑ 𝑟𝑘 = , 𝑓𝑜𝑟 𝑟 ≠ 1
𝑟−1
𝑘=0
Here, r=4x, n=4, so:
4
(4𝑥)5 − 1
𝐺(𝑥) = ∑(4𝑥)𝑘 = , 𝑓𝑜𝑟 4𝑥 ≠ 1
4𝑥 − 1
𝑘=0
But we can also just write it in expanded form or compact summation form.
However, since the sequence is short, the generating function can be written explicitly:
G(x)=1+4x+16x2+64x3+256x4
Alternatively, using powers of 4:
4

𝐺(𝑥) = ∑(4𝑥)𝑘 = 1 + 4𝑥 + (4𝑥)2 + (4𝑥)3 + (4𝑥)4

𝑘=0
[(4x)2=16x2, (4x)3=64x3, (4x)4=256x4, so this matches.]
Therefore, the generating function for the sequence 1,4,16,64,256 is:
G(x) = 1 + 4x + 16x2 + 64x3 + 256x4
Or,
4
(4𝑥)5 − 1
𝐺(𝑥) = ∑(4𝑥)𝑘 = , 𝑓𝑜𝑟 4𝑥 ≠ 1
4𝑥 − 1
𝑘=0

6(b) What is the solution of the recurrence relation together with the initial conditions
an = 4an–1 – 4an–2 for n ≥ 2, a0 = 6, a1 = 8?

Ans) We are given a linear homogeneous recurrence relation with constant coefficients:
an = 4an–1 – 4an–2 for n ≥ 2, with initial conditions a0 = 6, a1 = 8

Characteristic Equation
Assume a solution of the form an=rn. Substituting into the recurrence:
rn=4rn−1−4rn−2
Divide both sides by rn−2 (assuming r≠0 ):
r2=4r−4
or, r2−4r+4=0
or, (r-2)2=0
General Solution
When the characteristic equation has a repeated root r, the general solution is:
an=(A+Bn)rn
Here, r=2 , so:
an=(A+Bn)⋅2n
Initial conditions to solve for A and B
Using a0=6:
a0=(A+B⋅0)⋅20=A⋅1=A
Therefore, A=6
Using a1=8 :
a1=(A+B⋅1)⋅21=(6+B)⋅2=8
Solve for B:
2(6+B)=8
⇒12+2B=8
⇒2B=−4
⇒B=−2
Substituting A=6, B=−2:
an=(6−2n)⋅2n
an=2(3−n)⋅2n=(3−n)⋅2n+1
Therefore, an=(6−2n)⋅2n

1(b) Show that f(n) = n2 + 2n + 1 is of O(n2).

Ans) A function f(n) is said to be O(g(n)) if there exist positive constants C and n0 such that:
∣f(n)∣≤C⋅∣g(n)∣ for all n≥n0
In this case, we want to show that f(n)=n2+2n+1 is O(n2).
Analysing the function, we have:
f(n)=n2+2n+1
We want to show that this is bounded above by some constant multiple of n2 for sufficiently large n.
Comparing f(n) to n2:
f(n)=n2+2n+1≤n2+2n2+n2=4n2 for n≥1
For n≥1 , we have n≤n2 , so 2n≤2n2
Also, 1≤n2 when n≥1
Therefore,
n2+2n+1≤n2+2n2+n2=4n2
Or, f(n)≤4n2for all n≥1
Let C=4, n0=1
Then, for all n≥n0:
∣f(n)∣=f(n)=n2+2n+1≤4n2=C⋅n2
Therefore, f(n)=n2+2n+1 is O(n2). {Hence proved]

2021

2b) If f(n) is in O(g(n)) and g(n) is in O(h(n)), prove that f(n) is in O(h(n)).
Ans) As per the definition of Big-O, a function f(n) is said to be O(g(n)) if there exist positive constants
c and n0 such that ∣f(n)∣≤c⋅∣g(n)∣ for all n≥n0
Using f(n)=O(g(n)), by definition, there exist constants c1>0 and n1 such that:
∣f(n)∣ ≤ c1 ∣g(n)∣ for all n≥n1 (1)
Using g(n)=O(h(n)), by definition, there exist constants c2>0 and n2 such that:
∣g(n)∣ ≤ c2 ∣h(n)∣ for all n≥n2 (2)
Combining (1) and (2)
For all n ≥ max(n1,n2) , both inequalities (1) and (2) hold.
Substituting inequality (2) into (1):
∣f(n)∣ ≤ c1 ∣g(n)∣ ≤ c1 (c2∣h(n)∣) = (c1c2) ∣h(n)∣
So the constants c=c1c2>0 and n0=max (n1, n2) such that:
∣f(n)∣ ≤ c ∣h(n)∣ ∀ n≥n0
Therefore, by the definition of Big-O notation:
f(n)∈O(h(n)) [Hence proved]
2(c) Solve the following recurrence relation:
xn−5xn−1+6xn−2=0,
where x1=x2=1, for n≥3.
Ans) We are given the recurrence relation:
xn−5xn−1+6xn−2=0 for n≥3,
with initial conditions x1=1, x2=1.
Characteristic Equation
This is a linear homogeneous recurrence relation with constant coefficients.
Assuming a solution of the form xn=rn. Substituting into the recurrence:
rn−5rn−1+6rn−2=0
Dividing through by rn−2 (assuming r≠0):
r2−5r+6=0 [This is the characteristic equation].
Factoring it we get,
(r−2) (r−3) = 0
So the roots are:
r=2, r=3
General Solution
Since the roots are real and distinct, the general solution is:
xn = A⋅2n + B⋅3n
Using Initial Conditions
x1=1 and x2=1 to solve for A and B.
For n=1 :
x1=A⋅21+B⋅31 = 2A+3B=1 (Equation 1)
For n=2 :
x2=A⋅22+B⋅32 = 4A+9B=1 (Equation 2)
From Equation (1):
2A+3B=1
Multiply Equation (1) by 2:
4A+6B=2 (Equation 3)
Now subtracting (3) from (2), we get:
(4A+9B) − (4A+6B) = 1−2
⇒3B=−1
⇒B=−31
Substitute B=−31 into Equation (1):
1
2A+3(− 3) = 1
⇒2A−1=1
⇒2A=2
⇒A=1
Therefore, the final solution is:
1 1
xn=1⋅2n + (− 3)⋅3n = 2n− 3⋅3n
Simplifying, we get,
1
xn=2n−3n−1 [Since 3x3n=3n-1]
3a) There are 100 people in a certain room. In this group, 60 are men, 30 are young and 10 are
young men. It is known further that 40 are republicans, 20 are republican men, 15 are young
republicans and 5 are young republican men. Assume that each person is either a Republican or a
Democrat,
(i) How many are old women?
(ii) How many are old democratic women?

Ans) We are given a problem involving sets and need to use the principle of inclusion and exclusion.

Total people:
∣U∣=100
We have three binary attributes:
 Gender: Men (M) / Women (W)
 Age: Young (Y) / Old (O)
 Politics: Republican (R) / Democrat (D)
So every person falls into one of 8 categories: combinations of (M/W), (Y/O), (R/D).

Finding number of old women,

Old women=Women who are not young=W∩O
Total men = 60
So women = 100−60 = 40
Young people = 30
Young men = 10
So, young women = total young - young men = 30−10 = 20

Finding number of old democratic women,

Total women = 40
Young women = 20
So old women = 20 (as above)
Now we need to find how many of these 20 old women are democrats.
Given,
Total Republicans = 40
So, democrats = 100−40 = 60
Republican men = 20
So, republican women = 40−20 = 20
Young republicans = 15
Young republican men = 5
So, young republican women = 15−5 = 10
Thus, republican women = 20
Young republican women = 10
So, old republican women = 20−10 = 10

Therefore, Total old women = 20

Old Republican women = 10
So, old democratic women = 20−10 = 10