Prove that displaystylesum_{i=1}^{n} left(begin{array}{c}i 2end{array}right)=left(begin{array}{c}n+1 3end{array}right) forall ngeq2

Prove that displaystylesum_{i=1}^{n} left(begin{array}{c}i 2end{array}right)=left(begin{array}{c}n+1 3end{array}right) forall ngeq2

Question
Prove that \(\displaystyle\sum_{i=1}^{n} \left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}n+1\\ 3\end{array}\right)\)
\(\forall n\geq2\)

Answers (1)

2020-11-08

Step 1. Definitions
Definition combination
\(nCr=\left(\begin{array}{c}n\\ r\end{array}\right)=\frac{n!}{r!(n-r)!}\)
with \(n!=n\times(n-1)\times\dotsb\times2\times1\).
Pascal's equation
\(\left(\begin{array}{c}n+1\\ k\end{array}\right)=\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k-1\end{array}\right)\)
Step 2. Solution
To proof: \(\displaystyle\sum_{i=1}^{n} \left(\begin{array}{c}i\\ 2\end{array}\right)=(n+1)\) for all positive integers.
Proof by induction
Let P(n) be the statement "\(\displaystyle\sum_{i=1}^{n} \left(\begin{array}{c}i\\ 2\end{array}\right)=(n+1)\)".
Basis step. \(n=2\)
\(\displaystyle\sum_{i=1}^{n} \left(\begin{array}{c}i\\ 2\end{array}\right)=\displaystyle\sum_{i=1}^{2} \left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}i\\ 2\end{array}\right)+\left(\begin{array}{c}2\\ 2\end{array}\right)=0+1=1\)
\(\left(\begin{array}{c}n+1\\ 3\end{array}\right)=\left(\begin{array}{c}2+1\\ 3\end{array}\right)=\left(\begin{array}{c}3\\ 3\end{array}\right)=1\)
Thus P(2) is true.
Inductive step. Let P(k) be true.
\(\displaystyle\sum_{i=1}^{k} \left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}k+1\\ 3\end{array}\right)\)
We need to proof that \(P(k+1)\) is true.
\(\displaystyle\sum_{i=1}^{k+1} \left(\begin{array}{c}i\\ 2\end{array}\right)\)
\(=\displaystyle\sum_{i=1}^{k+1} \left(\begin{array}{c}i\\ 2\end{array}\right)+\left(\begin{array}{c}k+1\\ 2\end{array}\right)\)
\(\left(\begin{array}{c}k+1\\ 3\end{array}\right)+\left(\begin{array}{c}k+1\\ 2\end{array}\right) \ \text{Since P(k) is true}\)
\(=\left(\begin{array}{c}(k+1)+1\\ 3\end{array}\right) \ \text{Pascal's identity}\)
Thus \(P(k+1)\) is true.
Conclution. By the principle of methematical induction, P(n) is true for all positive integers n.

0

Relevant Questions

asked 2021-01-10
Prove that for \({n}\ge{2},{2}\cdot{\left(\begin{matrix}{n}\\{2}\end{matrix}\right)}+{\left(\begin{matrix}{n}\\{1}\end{matrix}\right)}={n}^{2}\)
asked 2021-01-02
Prove that \(\displaystyle\sum_{j=1}^{n} 2^{j}=2^{n+1}-2\)
\(\forall\geq1\)
asked 2021-06-05
Use the following Normal Distribution table to calculate the area under the Normal Curve (Shaded area in the Figure) when \(Z=1.3\) and \(H=0.05\);
Assume that you do not have vales of the area beyond \(z=1.2\) in the table; i.e. you may need to use the extrapolation.
Check your calculated value and compare with the values in the table \([for\ z=1.3\ and\ H=0.05]\).
Calculate your percentage of error in the estimation.
How do I solve this problem using extrapolation?
\(\begin{array}{|c|c|}\hline Z+H & Prob. & Extrapolation \\ \hline 1.20000 & 0.38490 & Differences \\ \hline 1.21000 & 0.38690 & 0.00200 \\ \hline 1.22000 & 0.38880 & 0.00190 \\ \hline 1.23000 & 0.39070 & 0.00190 \\ \hline 1.24000 & 0.39250 & 0.00180 \\ \hline 1.25000 & 0.39440 & 0.00190 \\ \hline 1.26000 & 0.39620 & 0.00180 \\ \hline 1.27000 & 0.39800 & 0.00180 \\ \hline 1.28000 & 0.39970 & 0.00170 \\ \hline 1.29000 & 0.40150 & 0.00180 \\ \hline 1.30000 & 0.40320 & 0.00170 \\ \hline 1.31000 & 0.40490 & 0.00170 \\ \hline 1.32000 & 0.40660 & 0.00170 \\ \hline 1.33000 & 0.40830 & 0.00170 \\ \hline 1.34000 & 0.41010 & 0.00180 \\ \hline 1.35000 & 0.41190 & 0.00180 \\ \hline \end{array}\)
asked 2021-05-14
Consider the accompanying data on flexural strength (MPa) for concrete beams of a certain type.
\(\begin{array}{|c|c|}\hline 11.8 & 7.7 & 6.5 & 6 .8& 9.7 & 6.8 & 7.3 \\ \hline 7.9 & 9.7 & 8.7 & 8.1 & 8.5 & 6.3 & 7.0 \\ \hline 7.3 & 7.4 & 5.3 & 9.0 & 8.1 & 11.3 & 6.3 \\ \hline 7.2 & 7.7 & 7.8 & 11.6 & 10.7 & 7.0 \\ \hline \end{array}\)
a) Calculate a point estimate of the mean value of strength for the conceptual population of all beams manufactured in this fashion. \([Hint.\ ?x_{j}=219.5.]\) (Round your answer to three decimal places.)
MPa
State which estimator you used.
\(x\)
\(p?\)
\(\frac{s}{x}\)
\(s\)
\(\tilde{\chi}\)
b) Calculate a point estimate of the strength value that separates the weakest \(50\%\) of all such beams from the strongest \(50\%\).
MPa
State which estimator you used.
\(s\)
\(x\)
\(p?\)
\(\tilde{\chi}\)
\(\frac{s}{x}\)
c) Calculate a point estimate of the population standard deviation ?. \([Hint:\ ?x_{i}2 = 1859.53.]\) (Round your answer to three decimal places.)
MPa
Interpret this point estimate.
This estimate describes the linearity of the data.
This estimate describes the bias of the data.
This estimate describes the spread of the data.
This estimate describes the center of the data.
Which estimator did you use?
\(\tilde{\chi}\)
\(x\)
\(s\)
\(\frac{s}{x}\)
\(p?\)
d) Calculate a point estimate of the proportion of all such beams whose flexural strength exceeds 10 MPa. [Hint: Think of an observation as a "success" if it exceeds 10.] (Round your answer to three decimal places.)
e) Calculate a point estimate of the population coefficient of variation \(\frac{?}{?}\). (Round your answer to four decimal places.)
State which estimator you used.
\(p?\)
\(\tilde{\chi}\)
\(s\)
\(\frac{s}{x}\)
\(x\)
asked 2021-05-17
How many permutations of three items can be selected from a group of six? Use the letters A,
B, C, D, E, and F to identify the items, and list each of the permutations of items B, D, and F.
asked 2021-06-11
\(\begin{array}{cc}\hline & \text{Afraid to walk at night?} \\ \hline & \text{Yes} & \text{No} & \text{Total} \\ \hline \text{Male} & 173 & 598 & 771 \\ \hline \text{Female} & 393 & 540 & 933 \\ \hline \text{Total} & 566 & 1138 & 1704 \\ \hline \text{Source:}2014\ GSS \end{array}\)
If the chi-square \((\chi 2)\) test statistic \(=73.7\) what is the p-value you would report? Use Table C.Remember to calculate the df first.
Group of answer choices
\(P>0.250\)
\(P=0.01\)
\(P<0.001\)
\(P<0.002\)

\(\begin{array}{|c|cc|}\hline & \text{Right-Tail Probability} \\ \hline df & 0.250 & 0.100 & 0.050 & 0.025 & 0.010 & 0.005 & 0.001 \\ \hline 1 & 1.32 & 2.71 & 3.84 & 5.02 & 6.63 & 7.88 & 10.83 \\ 2 & 2.77 & 4.61 & 5.99 & 7.38 & 9.21 & 10.60 & 13.82 \\ 3 & 4.11 & 6.25 & 7.81 & 9.35 & 11.34 & 12.84 & 16.27 \\ 4 & 5.39 & 7.78 & 9.49 & 11.14 & 13.28 & 14.86 & 18.47 \\ 5 & 6.63 & 9.24 & 11.07 & 12.83 & 15.09 & 16.75 & 20.52 \\ 6&7.84&10.64&12.59&14.45&16.81&18.55&22.46 \\ 7&9.04&12.02&14.07&16.01&18.48&20.28&24.32\\ 8&10.22&13.36&15.51&17.53&20.09&21.96&26.12 \\ 9&11.39&14.68&16.92&19.02&21.67&23.59&27.88 \\ 10&12.55&15.99&18.31&20.48&23.21&25.19&29.59 \\ 11&13.70&17.28&19.68&21.92&24.72&26.76&31.26 \\ 12&14.85&18.55&21.03&23.34&26.22&28.30&32.91 \\ 13&15.98&19.81&22.36 & 24.74 & 27.69 & 29.82 & 34.53 \\ 14 & 17.12 & 21.06 & 23.68 & 26.12 & 29.14 & 31.32 & 36.12 \\15 & 18.25 & 22.31 & 25.00 & 27.49 & 30.58 & 32.80 & 37.70 \\ 16 & 19.37 & 32.54 & 26.30 & 28.85 & 32.00 & 34.27 & 39.25 \\ 17 & 20.49 & 24.77 & 27.59 & 30.19 & 33.41 & 35.72 & 40.79 \\ 18 & 21.60 & 25.99 & 28.87 & 31.53 & 34.81 & 37.16 & 42.31 \\ 19 & 22.72 & 27.20 & 30.14 & 32.85 & 36.19 & 38.58 & 43.82 \\ 20 & 23.83 & 28.41 & 31.41 & 34.17 & 37.57 & 40.00 & 45.32 \\ \hline \end{array}\)
asked 2021-06-13
1. Who seems to have more variability in their shoe sizes, men or women?
a) Men
b) Women
c) Neither group show variability
d) Flag this Question
2. In general, why use the estimate of \(n-1\) rather than n in the computation of the standard deviation and variance?
a) The estimate n-1 is better because it is used for calculating the population variance and standard deviation
b) The estimate n-1 is never used to calculate the sample variance and standard deviation
c) \(n-1\) provides an unbiased estimate of the population and allows more variability when using a sample and gives a better mathematical estimate of the population
d) The estimate n-1 is better because it is use for calculation of both the population and sample variance as well as standard deviation.
\(\begin{array}{|c|c|}\hline \text{Shoe Size (in cm)} & \text{Gender (M of F)} \\ \hline 25.7 & M \\ \hline 25.4 & F \\ \hline 23.8 & F \\ \hline 25.4 & F \\ \hline 26.7 & M \\ \hline 23.8 & F \\ \hline 25.4 & F \\ \hline 25.4 & F \\ \hline 25.7 & M \\ \hline 25.7 & F \\ \hline 23.5 & F \\ \hline 23.1 & F \\ \hline 26 & M \\ \hline 23.5 & F \\ \hline 26.7 & F \\ \hline 26 & M \\ \hline 23.1 & F \\ \hline 25.1 & F \\ \hline 27 & M \\ \hline 25.4 & F \\ \hline 23.5 & F \\ \hline 23.8 & F \\ \hline 27 & M \\ \hline 25.7 & F \\ \hline \end{array}\)
\(\begin{array}{|c|c|}\hline \text{Shoe Size (in cm)} & \text{Gender (M of F)} \\ \hline 27.6 & M \\ \hline 26.9 & F \\ \hline 26 & F \\ \hline 28.4 & M \\ \hline 23.5 & F \\ \hline 27 & F \\ \hline 25.1 & F \\ \hline 28.4 & M \\ \hline 23.1 & F \\ \hline 23.8 & F \\ \hline 26 & F \\ \hline 25.4 & M \\ \hline 23.8 & F \\ \hline 24.8 & M \\ \hline 25.1 & F \\ \hline 24.8 & F \\ \hline 26 & M \\ \hline 25.4 & F \\ \hline 26 & M \\ \hline 27 & M \\ \hline 25.7 & F \\ \hline 27 & M \\ \hline 23.5 & F \\ \hline 29 & F \\ \hline \end{array}\)
asked 2020-11-14

Consider the bases \(B = \left(\begin{array}{c}\begin{bmatrix}2 \\ 3 \end{bmatrix}, \begin{bmatrix}3 \\ 5 \end{bmatrix}\end{array}\right) of R^2 \ and\ C = \left(\begin{array}{c}\begin{bmatrix}1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix}1\\0 \\ 1 \end{bmatrix}\end{array}, \begin{bmatrix}0 \\ 1\\1 \end{bmatrix}\right) of R^3\).
and the linear maps \(S \in L (R^2, R^3) \ and\ T \in L(R^3, R^2)\) given given (with respect to the standard bases) by \([S]_{E, E} = \begin{bmatrix}2 & -1 \\ 5 & -3\\ -3 & 2 \end{bmatrix} \ and\ [T]_{E, E} = \begin{bmatrix}1 & -1 & 1 \\ 1 & 1 & -1 \end{bmatrix}\) Find each of the following coordinate representations. \(\displaystyle{\left({b}\right)}{\left[{S}\right]}_{{{E},{C}}}\)
\(\displaystyle{\left({c}\right)}{\left[{S}\right]}_{{{B},{C}}}\)

asked 2021-05-18
Let P(k) be a statement that \(\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+...+\frac{1}{k\cdot(k+1)}=\)
for: The basis step to prove P(k) is that at k = 1, _____ is true.
for:Show that P(1) is true by completing the basis step proof. Left side of P(k) and Right side of P(k)
for: Identify the inductive hypothesis used to prove P(k).
for: Identify the inductive step used to prove P(k+1).
asked 2020-11-11

Use exponential regression to find a function that models the data. \(\begin{array}{|c|c|} \hline x & 1 & 2 & 3 & 4 & 5 \\ \hline f(x) & 14 & 7.1 & 3.4 & 1.8 & 0.8 \\ \hline \end{array}\)

...