Доказательство P=n! C помощью метода мат. индукции

Question

Олеся · Accepted Answer

1. Для одного элемента - справедливо 
P(1)=1!=1 
2. Предположим, что для некторого k выполняется соотношение P(k)=k! 
3. Докажем, что если (2), то P(k+1)=(k+1)! 
(k+1)й элемент можно поместить в перестановку либо первым, либо последним, либо в любой из (k-1) промежутков между элементами, то есть k*1+1+1=k+1 способом, и так для каждой из k! перестановок. 
Т. е. P(k+1)=k!*(k+1)=(k+1)! 
Доказано.