Solving Difference Equations using Omega CAS Explorer

Maxima’s ‘solve_rec‘ solves difference equation:

Fig. 1 Geometric Sequence

It solves initial-value problem as well:

Fig. 2 Fibonacci Sequence

Mathematica has ‘RSolve‘:

and ‘RSolveValue‘:

See also “Pandora’s Box“.

Fire & Water

Question:

When a forrest fire occurs, how many fire fighter should be sent to fight the fire so that the total cost is kept minimum?

Answer:

Suppose the fire starts at t=0; at t=t_1, the fire fighter arrives; the fire is extinguished later at t=t_2.

Let c_1, c_2, c_3 and x denotes the monetary damage per square footage burnt, the hourly wage per fire fighter, the one time cost per fire fighter and the number of fire fighters sent respectively. The total cost consists damage caused by the fire, the wage paid to the fire fighters and the one time cost of the fire fighters:

c(x) = c_1\cdot(total square footage burnt) +\;c_2\cdot (t_2-t_1)\cdot x + c_3\cdot x.

Notice t_2-t_1, the duration of fire fighting.

Assume the fire ignites at a single point and quickly spreads in all directions with flame velocity v_*, the growing square footage of engulfed circular area is a function of time. Namely,

b(t) = \pi r^2  = \pi (v_* t) ^2 = \pi v_*^2 t^2 \overset{k=\pi v_*^2}{=} k t^2.

Its burning rate

v_b(t) = b'(t) = 2 k t \overset{\alpha = 2 k}{=} \alpha t.\quad\quad\quad(1)

However, after the arrival of x fire fighters, \alpha is reduced by \beta x, an amount that is directly proportional to the number of fire fighters on the scene. The reduction of \alpha reflects the fire fighting efforts exerted by the crew. As a result, for t > t_1, v_b(t) declines along the line described by

v_b(t) = (\alpha-\beta x)t + d

where \alpha-\beta x <0. Or equivalently,

\beta x - \alpha >0.\quad\quad\quad(2)

Moreover, the fire is extinguished at t_2 suggests that

v_b(t_2) = 0 \implies (\alpha-\beta x) t_2 + d =0 \implies d = -(\alpha-\beta x)t_2.

i.e.,

\forall t_1< t \le t_2, v_b(t) = (\alpha-\beta x) t - (\alpha-\beta x) t_2=(\alpha-\beta x) (t-t_2).\quad\quad\quad(3)

Combine (1) and (3),

v_b(t) = \begin{cases} \alpha t, \quad\quad\quad\quad\quad\quad\quad\quad0\le t \le t_1\\ (\alpha-\beta x)(t-t_2),\quad\quad t_1< t \le t_2 \end {cases}.

It is further assumed that

v_b(t) is continuous at t=t_1.\quad\quad\quad(4)

We illustrate v_b(t) in Fig. 1.

Fig. 1

The fact that v_b(t) is continuous at t_1 means

\lim\limits_{t \to t_1^+}v_b(t)=(\alpha-\beta x)(t_1-t_2) = \lim\limits_{t \to t_1^-}v_b(t) = h \implies (\alpha-\beta x) (t_1-t_2)=h.

That is,

t_2-t_1=\frac{h}{\beta x - \alpha}.\quad\quad\quad(5)

The area of triangle in Fig. 1 represents b(t_2), the total square footage damaged by the fire. i.e.,

b(t_2) =\frac{1}{2}t_1 h + \frac{1}{2}(t_2-t_1)h\overset{(5)}{=}\frac{1}{2}t_1 h+ \frac{1}{2}\frac{h^2}{\beta x-\alpha}.\quad\quad\quad(6)

Consequently, the total cost

c(x)= c_1 b(t_2) + c_2 x (t_2-t_1)  + c_3 x \overset{(6), (5)}{=}\frac{c_1 t_1 h}{2} + \frac{c_1 h^2}{2(\beta x-\alpha)} + \frac{c_2 h x}{\beta x-\alpha} + c_3 x.

To minimize the total cost, we seek a value x where function c attains its minimum value c(x).

From expressing x as

x = \frac{1}{\beta}\beta x = \frac{1}{\beta}({\beta x-\alpha +\alpha} )= \frac{1}{\beta}(\beta x -\alpha) + \frac{\alpha}{\beta},

we obtain

\frac{c_2 h x}{\beta x-\alpha} = \frac{c_2 h}{\beta x-\alpha}(\frac{1}{\beta}(\beta x - \alpha) + \frac{\alpha}{\beta})=\frac{c_2 h}{\beta} + \frac{c_2 \alpha h}{\beta(\beta x-\alpha)},\quad\quad\quad(7)

c_3 x = \frac{c_3}{\beta}(\beta x-\alpha) + \frac{c_3 \alpha}{\beta}.\quad\quad\quad(8)

It follows that

c(x) = \underbrace{\frac{c_1 t_1 h}{2} + \frac{c_1 h^2}{2(\beta x-\alpha)}}_{c_1\cdot(6)} + \underbrace{\frac{c_2 h}{\beta}+\frac{c_2 \alpha h}{\beta(\beta x - \alpha)}}_{(7)} + \underbrace{\frac{c_3}{\beta}(\beta x-\alpha) + \frac{c_3 \alpha}{\beta}}_{(8)}

=\frac{c_1 t_1 h}{2} + \frac{c_2 h}{\beta} + \frac{c_3 \alpha}{\beta} + \underline{\frac{c_1 \beta  h^2+2 c_2 \alpha h}{2\beta(\beta x - \alpha)} + \frac{c_3(\beta x-\alpha)}{\beta}}.

Hence, to minimize c(x) is to find the x that minimizes \frac{c_1\beta h^2+2 c_2\alpha h }{2\beta(\beta x - \alpha)} + \frac{c_3(\beta x - \alpha)}{\beta}.

Since \frac{c_1\beta h^2+2 c_2\alpha h }{2\beta(\beta x - \alpha)} \cdot \frac{c_3(\beta x - \alpha)}{\beta}=\frac{(c_1 \beta h^2+2 c_2 \alpha h)c_3}{2\beta^2} , a constant, by the following theorem:

For positive quantities a_1, a_2, ..., a_n, c_1, c_2, ..., c_n and positive rational quantities p_1, p_2, ..., p_n, if a_1^{p_1}a_2^{p_2}...a_k^{p_k} is a constant, then c_1a_1+c_2a_2+...+c_na_n attains its minimum if \frac{c_1a_1}{p_1} = \frac{c_2a_2}{p_2} = ... = \frac{c_na_n}{p_n}.

(see “Solving Kepler’s Wine Barrel Problem without Calculus“), we solve equation

\frac{c_1\beta h^2+2 c_2\alpha h }{2\beta(\beta x - \alpha)} = \frac{c_3(\beta x - \alpha)}{\beta}

for x:

Fig. 2

From Fig. 2, we see that x =\frac{\alpha}{\beta} - \frac{\sqrt{\beta c_1 c_3 h^2+2\alpha c_2 c_3 h}}{\sqrt{2}\beta c_3} \implies \beta x - \alpha < 0, contradicts (2).

However, when x =\frac{\sqrt{\beta c_1 c_3 h^2+2\alpha c_2 c_3 h}}{\sqrt{2}\beta c_3} + \frac{\alpha}{\beta}=\sqrt{\frac{\beta c_1 h^2 + 2 \alpha c_2 h}{2\beta^2 c_3}} + \frac{\alpha}{\beta}, \beta x-\alpha is a positive quantity. Therefore, it is

x \overset{h=\alpha t_1}{=} \alpha \sqrt{\frac{\beta c_1 t_1^2 + 2 c_2 t_1}{2\beta^2 c_3}} + \frac{\alpha}{\beta}

that minimizes the total cost.