#ATTENDANCE QUIZ FOR LECTURE 16 of Dr. Z.'s Math454(02) Rutgers University

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p16
#with an attachment called
#p16FirstLast.txt
#(e.g. p16DoronZeilberger.txt)

#Right after finishing watching the lecture but no later than Oct. 30, 2020, 8:00pm


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 9

PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH, BY THE ANSWER



#ATTENDANCE Q. #1 for LECTURE 16 part 1
#convert 6*f(n)+12f(n+1)+18f(n+3)=0 into explicit format 

#ANSWER to Q. #1:	

# f(n+3) = 0*f(n+2) - 2/3*f(n+1) - 1/3*f(n)




#ATTENDANCE Q. #2 for LECTURE 16 part 1
#find f(5) and f(6)

#ANSWER to Q. #2:

#f(n+2) = 3f(n-1) - 4f(n-2)  f(0) = 1, f(1) = -2
#f(3) = -22, f(4) = -26

#f(5) = -78+88 = 10
#f(6) = 30+104 = 134




#ATTENDANCE Q. #3 for LECTURE 16 part 1
#F(10^6)? What is f(10^6)? How long did they take?

#ANSWER to Q. #3:

#For me, f(10^6) doesn't work and says there's an error about too many levels of recursion
#F(10^6) = 2458745050599682757015378035481882035383438999154580592871756279661111973933372432322733427701904766[...300831 digits...]4827529846518999275111180114315872236327482873665581735845785170957134521733463038891202865307177894
#time(F(10^6)) = 487.359
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


#ATTENDANCE Q. #1 for LECTURE 16 part 2
#Operator ope(N) such that ope(N) f(n) = 0 for f(n+1000)=f(n+999)+5*f(n) => f(n+1000)-f(n+999)-5*f(n)=0

#ANSWER to Q. #1:

#ope(N) = N^1000 - N^999 - 5




#ATTENDANCE Q. #2 for LECTURE 16 part 2
#characterize the sequence(s) that satisfy a (homogeneous) recurrence
#of order zero

#ANSWER to Q. #2:

#The only non-zero coefficient will be in front of f(n), i.e. 0*f(n+k) + 0*f(n+k-1) + ... + 0*f(n+1) + c*f(n) = 0, c != 0
#Solving for f(n), we find that 0/c = 0 = f(n), which means that for all n, f(n) = 0 (no remembering yesterday).
#So, the sequence will always be 0,0,0,0,0,0,0,...




#ATTENDANCE Q. #3 for LECTURE 16 part 2
#can you prove that d(n)/n! -> 1/e?

#ANSWER to Q. #3:

#Let N be the number of permutations of n, N(x) the number of permutations of {1,...,x}, and D(n)=d(n) be the number of derangements, 
#and C(a,b) the binomial operator
#We have that D(n) = N - C(n,1)*N(1) + C(n,2)*N(2) - ... + (-1)^n*C(n,n)*N(1,2,3,...n)
#This is via Principle of inclusion-exclusion
#D(n) = N - C(n,1)(n-1)! + C(n,2)(n-2)! - ... + (-1)^n*C(n,n)*(n-n)!
#We can replace N with n! (definition of number of permutations of n) and get:
#D(n) = n!(1 - 1/1! + 1/2! - 1/3! + ... (-1)^n(1/n!))
#Divide everything by n! to get d(n)/n! -> d(n)/n! = 1 - 1/1! + 1/2! - 1/3! + ... (-1)^n(1/n!)
#This is the Maclaurin series expansion of f(x) = e^x, a.k.a. sum_{n=0 to infinity} of (x!/n!), where in our case, x=-1.
#So, this series converges toward e^-1 or 1/e as n -> infinity.  (proof via uic.edu)




#ATTENDANCE Q. #4 for LECTURE 16 part 2
#OEIS A number of the involutions sequence?

#ANSWER to Q. #4: A000085




#ATTENDANCE Q. #5 for LECTURE 16 part 2
#Find the operators in N and N^(-1) annihilated by w(n)

#ANSWER to Q. #5:

#w(n+2)-w(n+1)-(n+1)*w(n)=0 --> involutions are annihilated by  N^2 - N - (n+1)  [in N]

#doing N^(-1)*( N^2-N-(n+1) ) gives annihilation by  N - 1 - (n-1)*N^(-1)  [in N^(-1)]





#ATTENDANCE Q. #6 for LECTURE 16 part 2
#Look up the syntax of ZeilbergerRecurrence

#ANSWER to Q. #6:

#ZeilbergerRecurrence(T, n, k, f, l..u)
T-hypergeometric term of n and k
n-name
k-name
En-name; denote the shift operator with respect to n
f-name of the recurrence function
l..u-range for k
'Zpair'-list of two elements specifying a Z-pair for T