MathDB
Problems
Contests
Undergraduate contests
Putnam
1958 November Putnam
A1
Putnam 1958 November A1
Putnam 1958 November A1
Source: Putnam 1958 November
July 19, 2022
Putnam
function
recurrence relation
Problem Statement
Let
f
(
m
,
1
)
=
f
(
1
,
n
)
=
1
f(m,1)=f(1,n)=1
f
(
m
,
1
)
=
f
(
1
,
n
)
=
1
for
m
≥
1
,
n
≥
1
m\geq 1, n\geq 1
m
≥
1
,
n
≥
1
and let
f
(
m
,
n
)
=
f
(
m
−
1
,
n
)
+
f
(
m
,
n
−
1
)
+
f
(
m
−
1
,
n
−
1
)
f(m,n)=f(m-1, n)+ f(m, n-1) +f(m-1 ,n-1)
f
(
m
,
n
)
=
f
(
m
−
1
,
n
)
+
f
(
m
,
n
−
1
)
+
f
(
m
−
1
,
n
−
1
)
for
m
>
1
m>1
m
>
1
and
n
>
1
n>1
n
>
1
. Also let
S
(
n
)
=
∑
a
+
b
=
n
f
(
a
,
b
)
a
≥
1
and
b
≥
1.
S(n)= \sum_{a+b=n} f(a,b) \,\,\;\; a\geq 1 \,\, \text{and} \,\; b\geq 1.
S
(
n
)
=
a
+
b
=
n
∑
f
(
a
,
b
)
a
≥
1
and
b
≥
1.
Prove that
S
(
n
+
2
)
=
S
(
n
)
+
2
S
(
n
+
1
)
for
n
≥
2.
S(n+2) =S(n) +2S(n+1) \,\, \; \text{for} \, \, n \geq 2.
S
(
n
+
2
)
=
S
(
n
)
+
2
S
(
n
+
1
)
for
n
≥
2.
Back to Problems
View on AoPS