# Thread: let n >= 4 be an integer, prove..

1. ## let n >= 4 be an integer, prove..

let n >= 5 be an integer, prove..

a) using algebra
b) using combinatorial argument

for part a) all you have to do is substitute 5 for n and you have:

but for part b) i have to make up a story.. need help please...

2. Originally Posted by memee4eva
let n >= 5 be an integer, prove..

a) using algebra
b) using combinatorial argument

for part a) all you have to do is substitute 5 for n and you have:

but for part b) i have to make up a story.. need help please...

3. Hello, memee4eva!

Let $n \geq 5$ be an integer,

prove: . ${n\choose1} + 6{n\choose2} + 6{n\choose3} \:=\:n^3$

a) using algebra
b) using combinatorial argument
(a) You proved it true for $n = 5$ only.

We have: . ${n\choose1} + 6{n\choose2} + 6{n\choose3}$

That is: . $n + 6\!\cdot\!\frac{n(n-1)}{2} + 6\!\cdot\!\frac{n(n-1)(n-2)}{6}$

. . . . $= \;\;n + 3n(n-1) + n(n-1)(n-2)$

. . . . $= \;\;n + 3n^2 - 3n + n^3 - 3n^2 + 2n$

. . . . $=\;\; n^3$

And that is an algebraic proof.

4. Hello memee4eva
Originally Posted by memee4eva
let n >= 5 be an integer, prove..

a) using algebra
b) using combinatorial argument

for part a) all you have to do is substitute 5 for n and you have:

but for part b) i have to make up a story.. need help please...
For argument (b) here's the scenario: A password consists of $3$ characters. How many possible passwords are there, if $n$ characters are available to choose from, repetition being allowed?

Method 1

Each of the $3$ positions in the password can be filled in $n$ ways. There are therefore $n^3$ possible passwords.

Method 2

A If repetition is not allowed, there are $\binom{n}{3}$ ways of choosing which $3$ different characters to use; and $3! = 6$ ways of arranging them to form the password. There are therefore $6\binom{n}{3}$ passwords where all three characters are different.

B If two characters are repeated, and the third one is different, there are $\binom{n}{2}$ ways of choosing which two characters will make up the password; then there are two ways of choosing which of these character is the one to be repeated; finally, there are then three ways of choosing the position to be occupied by the non-repeated character. So there are $6\binom{n}{2}$ passwords that use two different characters.

C There are $\binom{n}{1}$ ways of choosing a single character, and therefore $\binom{n}{1}$ passwords made up of just one character.

The total number of passwords is therefore $\binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3}$