Advanced book on Mathematics Olympiad

6.2 Binomial Coefficients and Counting Methods 297

(

n

m

)

q

=

(

n− 1

m

)

q

+qn−m

(

n− 1

m− 1

)

q

,

gives rise to what is called theq-Pascal triangle.

859.Prove that
(
2 k
k

)

=

2

π

∫ π 2

0

(2 sinθ)^2 kdθ.

860.Consider the triangularn×nmatrix

A=

⎛

⎜⎜

⎜⎜

⎜

⎝

111 ··· 1

011 ··· 1

001 ··· 1

..

.

..

.

..

.

... ..

.

000 ··· 1

⎞

⎟⎟

⎟⎟

⎟

⎠

.

Compute the matrixAk,k≥1.

861.Let(Fn)nbe the Fibonacci sequence,F 1 =F 2 =1,Fn+ 1 =Fn+Fn− 1. Prove that
for any positive integern,

F 1

(

n

1

)

+F 2

(

n

2

)

+···+Fn

(

n

n

)

=F 2 n.

862.For an arithmetic sequencea 1 ,a 2 ,...,an,...,letSn=a 1 +a 2 +···+an,n≥1.
Prove that
∑n

k= 0

(

n

k

)

ak+ 1 =

2 n

n+ 1

Sn+ 1.

863.Show that for any positive integern, the number

Sn=

(

2 n+ 1

0

)

· 22 n+

(

2 n+ 1

2

)

· 22 n−^2 · 3 +···+

(

2 n+ 1

2 n

)

· 3 n

is the sum of two consecutive perfect squares.

864.For a positive integerndefine the integersan,bn, andcnby

an+bn^3

√

2 +cn^3

√

4 =( 1 +^3

√

2 +^3

√

4 )n.

Prove that

2 −

n 3 ∑n

k= 0

(

n

k

)

ak=

⎧

⎪⎨

⎪⎩

an ifn≡ 0 (mod 3),

bn^3

√

2ifn≡ 2 (mod 3),

cn^3

√

4ifn≡ 1 (mod 3).