I'm learning about permutations, and have been playing around with them trying to find a recursive definition of $P(n+1,r)$ in terms of $P(n,r)$, where $P(n,r)$ represents the number of $r$ permutations of a set of $n$ elements.
My intuition is as follows:
$P(n+1,r) = (n+1)*P(n,r)$
Here is my "Proof":
Let $S$ be a set of $n+1$ elements. For each element $s_{i} \in S$, we have that $S-\{s_{i}\}$ has $n$ elements. Thus there are $P(n,r)$ r-permutations of the set $S-\{s_{i}\}$. There are $n+1$ choices for $s_{i}$, so there are $(n+1)*P(n,r)$ r-permutations in $S$.
This is clearly wrong. For example, $P(4,2) = 12 \not= 4*6 = 4*P(3,2)$
So where is my reasoning incorrect?
For $P(n+1,r)$, you want to choose permutations of $r$ elements out of a set of $n+1$. In your reasoning, after choosing the first element ($n+1$ options), you have to choose only $r-1$ left. So you need $P(n,r-1)$ next rather than $P(n,r)$. Then the final answer is $(n+1)*P(n,r-1)$.