• Non ci sono risultati.

Then the strings which start with Head and have d runs all of even lengths are counted by the solutions of the equation 2x1+ 2x2

N/A
N/A
Protected

Academic year: 2021

Condividi "Then the strings which start with Head and have d runs all of even lengths are counted by the solutions of the equation 2x1+ 2x2"

Copied!
1
0
0

Testo completo

(1)

Problem 11754

(American Mathematical Monthly, Vol.121, February 2014) Proposed by D. Beckwith (USA).

When a fair coin is tossed n times, let P (n) be the probability that the lengths of all runs (maximal constant strings) in the resulting sequence are of the same parity as n. Prove that

P (n) =

 (1/2)n/2 if n is even, (1/2)n−1Fn if n is odd, where Fn is the nth Fibonacci number.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Assume first that n is even. Then the strings which start with Head and have d runs all of even lengths are counted by the solutions of the equation

2x1+ 2x2+ · · · + 2xd= n

where each xi is a positive integer. The number of such solutions is n/2−1d  and thus

P (n) = 2 2n

n/2

X

d=1

n/2 − 1 d − 1



= 2n/2−1

2n−1 = (1/2)n/2.

Assume now that n is odd. Then the strings which start with Head and have d runs all of odd lengths are counted by the solutions of the equation

(2x1− 1) + (2x2− 1) + · · · + (2xd− 1) = n

where each xi is a positive integer. The number of such solutions is (n+d)/2−1d−1  when d is odd and it is zero otherwise. Thus, by setting d = 2j + 1, we obtain

P (n) = 2 2n

(n−1)/2

X

j=0

(n + (2j + 1))/2 − 1 2j



= 1

2n−1

(n−1)/2

X

j=0

(n − 1)/2 + j 2j



= (1/2)n−1Fn,

where the last equality is due to the following fact. If A(t) =P

k≥0aktk then

m

X

j=0

m + j 2j



ak= [tm] 1 1 − t A

 t

(1 − t)2

 .

Hence for A(t) = 1/(1 − t), we obtain

m

X

j=0

m + j 2j



= [tm] 1 − t

1 − 3t + t2 = [t2m]F (t) − F (−t)

2t = F2m+1.

where F (t) = 1/(1 − t − t2) =P

k≥0Fktk. 

Riferimenti

Documenti correlati

decreases the activation energy of the forward reaction and increases the activation energy of the reverse reaction.. increases the activation energy of the forward reaction

Title: Effect of the change of social environment on the behavior of a captive brown bear (Ursus arctos).. Article Type: Original

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. Our proof is inspired

(American Mathematical Monthly, Vol.119, November 2012) Proposed by Mircea Merca (Romania). Let p be the Euler partition function, i.e., p(n) is the number of nondecreasing lists

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let a(n, k) be the number

2 The second chapter, after a discussion on the model concept and a description of the OSEC model, focuses on what are the models of structural equations (MES), analyzing

We hold these truths to be self-evident, that all men are created equal, that they are endowed by their creator with certain inalienable rights, that among these are life, liberty,