The exact problem:
Prove: The sum of the 2nd entries from any two successive rows of Pascal's triangle is equal to a square. (Note: the initial entry in any row is called the 0th entry.)
I started with translating this into an equation:
(n choose 2) + ([n+1] choose 2) = n squared
I then tried to solve by induction, and I proved the base case, but couldn't get any further.
Am I on the right path?
Prove: The sum of the 2nd entries from any two successive rows of Pascal's triangle is equal to a square. (Note: the initial entry in any row is called the 0th entry.)
I started with translating this into an equation:
(n choose 2) + ([n+1] choose 2) = n squared
I then tried to solve by induction, and I proved the base case, but couldn't get any further.
Am I on the right path?
-
No, don't use induction. Just use some algebra:
(n C 2) + ((n + 1) C 2)
= n(n - 1) / 2 + (n + 1)n / 2
= n(n - 1 + n + 1) / 2
= 2n^2 / 2
= n^2
EDIT: Recall that:
n! = n(n - 1)! = n(n - 1)(n - 2)!
So:
n! / (n - 2)! = n(n - 1)
n! / [(n - 2)! 2!] = n(n - 1) / 2
n C 2 = n(n - 1) / 2
That's what I used here. In general, n C k can be written as:
n * (n - 1) * (n - 2) * ... * (n - k + 1) / k!
I just used the k = 2 case.
(n C 2) + ((n + 1) C 2)
= n(n - 1) / 2 + (n + 1)n / 2
= n(n - 1 + n + 1) / 2
= 2n^2 / 2
= n^2
EDIT: Recall that:
n! = n(n - 1)! = n(n - 1)(n - 2)!
So:
n! / (n - 2)! = n(n - 1)
n! / [(n - 2)! 2!] = n(n - 1) / 2
n C 2 = n(n - 1) / 2
That's what I used here. In general, n C k can be written as:
n * (n - 1) * (n - 2) * ... * (n - k + 1) / k!
I just used the k = 2 case.
-
This works for n ≥ 1. Remember that C(n,k) = 0 if n < k. The proof is actually quite simple algebraically:
C(n,2) + C(n+1,2)
n!/(2!(n - 2)!) + (n+1)!/(2!(n-1)!)
(1/2)(n(n-1) + (n+1)n)
(1/2)(n² - n + n² + n)
(1/2)(2n²)
n².
I'd have liked to do an combinatorial proof, but I can't think of a situation for the LHS.
C(n,2) + C(n+1,2)
n!/(2!(n - 2)!) + (n+1)!/(2!(n-1)!)
(1/2)(n(n-1) + (n+1)n)
(1/2)(n² - n + n² + n)
(1/2)(2n²)
n².
I'd have liked to do an combinatorial proof, but I can't think of a situation for the LHS.