Question

Let T(n) = 1 + 2 + ... + n be the n-th triangular number. For...

Let T(n) = 1 + 2 + ... + n be the n-th triangular number. For example, t(1) = 1, t(2) = 3, t(3) = 6... T(n)= n(n+1)/ 2

a. Show that T(2n) = 3T(n) + T(n-1)

b. Show that T(1) + T(2) + T(n) = (n(n+1)(n+2))/6

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Solve the following recurrences: (a) T(n) = T(n=2) + O(n), with T(1) = 1. Solve this...
Solve the following recurrences: (a) T(n) = T(n=2) + O(n), with T(1) = 1. Solve this two times: one with the substitution method and one with the master theorem from CLRS. When you use the master theorem, carefully show the values for the parameters a; b. For the following cases you can use your preferred method. In either case, show your work: (b) T(n) = 2T(n/2) + O(1), T(1) = 1. (c) T(n) = 3T(n/2) + O(1), T(1) = 1....
Suppose T(n) is defined recursively as: T(0) = 1 T(n) = 3T(n-3) + O(n) True or...
Suppose T(n) is defined recursively as: T(0) = 1 T(n) = 3T(n-3) + O(n) True or false: T(n) ∈ O(2n)
Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored...
Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored tiles to visually prove the following for .(n=5) [a] The nth hexagonal number is equal to the nth square number plus twice the (n-1) ^th triangular number. Also provide an algebraic proof of this theorem for full credit [b] The nth hexagonal number is equal to the (2n-1)^th triangular number. Also provide an algebraic proof of this theorem for full credit. Please use (...
Show that gcd(u_n, u_n+2) = 1 or 2, where u_n denotes the n th Fibonacci number.
Show that gcd(u_n, u_n+2) = 1 or 2, where u_n denotes the n th Fibonacci number.
Let A ⊆ {1, 2, 3, . . . , 2n}, |A| = n + 1,...
Let A ⊆ {1, 2, 3, . . . , 2n}, |A| = n + 1, then there exists two elements a, b ∈ A such that either a | b or b | a.
If n is a natural number, then 1 * 5 + 2 * 6 + 3...
If n is a natural number, then 1 * 5 + 2 * 6 + 3 * 7 + ------ + n(n +4) = n(n+1)(2n+13)/6.
Let P(n) be the statement that 12 + 22 +· · ·+n 2 = n(n+ 1)(2n+...
Let P(n) be the statement that 12 + 22 +· · ·+n 2 = n(n+ 1)(2n+ 1)/6 for the positive integer n. Prove that P(n) is true for n ≥ 1.
Let n = 391 = 17x23 (which is not a prime number) a. Using Maple to...
Let n = 391 = 17x23 (which is not a prime number) a. Using Maple to show that 2n-1 is not congruent to 1 (mod n).    b. Use Maple Find a non-zero exponent j such that 2j ≡1 (mod n).
Apply the master method (I need detailed steps, stating which case, values of Є, etc…). T(n)=T(2n/3)+1...
Apply the master method (I need detailed steps, stating which case, values of Є, etc…). T(n)=T(2n/3)+1 T(n) =3T(n/4)+ n *logn T(n)= 9T(n/3)+n
Automata Please prove the following by induction. Let S(n) be the sum of squares from 1...
Automata Please prove the following by induction. Let S(n) be the sum of squares from 1 to n, i.e., S(n)=1^2 + 2^2 + 3^2 + ... + n^2 Then S(n) = n(n+1)(2n+1)/6 = (2n^3+3n^2+n)/6