#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 22
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

#############
# Problem 1 #
#############

# The recurrence is
# (1-p)x(n-1) - x(n) + px(n+1) = 0

# The roots of the characteristic equation are
# (1 +- (2p-1))/(2p)
# which simplifies to 1 and (1-p)/p.

# If p is not equal to 1/2, there are two distinct roots, so the
# solution is of the form x(i) = c1 + c2*((1-p)/p)^i.

# From the boundary conditions we have

# c1 + c2 = 0

# and

# c1 + c2*((1-p)/p)^N = 1

# so that c2 = 1/(((1-p)/p)^N - 1) and c1 = -1/(((1-p)/p)^N - 1)
# and x(i) = -1/(((1-p)/p)^N - 1) + (1-p)^i/(p^i(((1-p)/p)^N - 1)).

# If p is equal to 1/2, then there is a double root (which is 1), so the solution
# is of the form

# x(i) = c1 + i*c2
# From the boundary conditions we have

# c1 = 0

# and

# c1 + N*c2 = 1

# so that c2 = 1/N and x(i) = i/N.

#############
# Problem 3 #
#############

# The reccurrence is
# (1-p)x(n-1) - x(n) + px(n+1) = -1

# The characteristic polynomial and roots are the same as in Problem
# 1.

# If p is not equal to 1/2 then the roots are distinct, so the
# solution is of the form

# x(i) = c1 + c2*((1-p)/p)^i + PS(i)

# We may guess a particular solution of the form x(i) = Ki. In this
# case we get K = 1/(1-2p). So

# x(i) = c1 + c2((1-p)/p)^i + i/(1-2p).

# The boundary conditions give

# c1 + c2 = 0

# and

# c1 + c2*((1-p)/p)^N + N/(1-2p) = 0

# so that c2 = (N/(1-2p))/(((1-p)/p)^N - 1) and c1 = -c2.

# If p = 1/2 then the solution is of the form

# x(i) = c1 + ic2 + PS(i)
# It is easy to guess the particular solution -i^2, so that

# x(i) = c1 + ic2 - i^2.

# The boundary conditions give

# c1 = 0

 # and

# c1 + Nc2 - N^2 = 0

# We conclude that c2 = N and

# x(i) = iN - i^2.

#############
# Problem 5 #
#############

VDW:=proc(p,N) local x, i, L, vars, eqns, solns:
    vars := [seq(x[i], i=0..N)]:
    L := VW(p, N):
    eqns := {x[0]=0, x[N]=0,
         seq(L[i+1]*x[i]=p*L[i+2]*(x[i+1]+1)+(1-p)*L[i]*(x[i-1]+1), i=1..N-1)}:
    solns := solve(eqns, vars):
    return subs(convert(solns[1], set), vars):
end:


# From my c22.txt:

VW := proc(p, goal) local v, eqs, vars, solns:
    vars := [seq(v[i], i=0..goal)]:
    eqs := {v[0]=0, v[goal]=1}:
    eqs := eqs union {seq(p*v[i+1] + (1-p)*v[i-1] = v[i], i=1..goal-1)}:
    solns := solve(eqs, vars):
    return subs(convert(solns[1], set), vars):
end:

#############
# Problem 6 #
#############

# Conjecture: The expected duration of a winning game is N^2 - i^2
# turns.

#############
# Problem 7 #
#############

# Proof:
# The recurrence is

# ix(i)/N = (1/2)[(i-1)x(i-1) + (i+1)x(i+1)]/N

# Simplifying, we get
# (i+1)x(i+1) - 2ix(i) + (i-1)x(i-1) = 0.

# It can now be seen that N^2 - i^2 satisfies the recurrence and the
# base case x(N) = 0.