Display section on first chapter page when that page number is odd

Question

Using \documentclass[twoside]{report}, I would like the following headers:

• on the left, for even pages Part Title: Chapter Title
• on the right, for odd pages Section Title

In the MWE, I'm mostly getting what I want, based on these questions:

• How to get part name in LaTeX ?
• Why doesn't \pagestyle{empty} work on the first page of a chapter?

However, as seen on pages 3 and 7, when a chapter begins on an odd-numbered page, the section title doesn't appear in the header. Given the behavior on page 6, headings are working for even-numbered chapter start pages.

How do I get the section title to appear in the header on odd-numbered pages where a chapter begins?

MWE

    \documentclass[twoside]{report}
    \usepackage{fancyhdr}
    \usepackage[english]{babel}
    \usepackage{blindtext}
    \usepackage{etoolbox}

    %https://tex.stackexchange.com/a/13395/56480
    \let\Oldpart\part
    \newcommand{\parttitle}{}
    \renewcommand{\part}[1]{
        \Oldpart{#1}
        \renewcommand{\parttitle}{#1}   
    }

    \pagestyle{fancy}
    \fancyhf{}
    \renewcommand{\chaptermark}[1]{\markboth{\parttitle: #1}{}}
    \renewcommand{\sectionmark}[1]{\markright{#1}}

    \fancyhead[RO]{\rightmark}       
    \fancyhead[LE]{\leftmark}  
    \fancyfoot[C]{\thepage}

    %https://tex.stackexchange.com/a/19741/56480
    \patchcmd{\chapter}{plain}{fancy}{}{}

    \begin{document}

    \tableofcontents
    \part{First Part}
    \chapter{First Chapter}
    \blindtext[1]
    \section{First Section}
    \blindtext[5]
    \section{Second Section}
    \blindtext[7]
    \chapter{Second Chapter}
    \blindtext[1]
    \section{Third Section}
    \blindtext[2]
    \chapter{Third Chapter}
    \blindtext[1]
    \section{Fourth Section}
    \blindtext[5]\end{document}

Answer 1

A mark command sets three variables: \topmark (last mark of the previous page), firstmark (first mark on the current page) and \botmark (last mark on the current page). \rightmark uses the \firstmark set by \markright or the second argument of \markboth. On a chapter page the first call of \markboth is done by \chapter with an empty second argument to reset the header entry.

If it is alright to use the last section occurring on a page you could define a command \rightbotmark using \botmark instead \firstmark.

\makeatletter
\providecommand*{\rightbotmark}{\expandafter\@rightmark\botmark\@empty\@empty}
\makeatother

and then

\fancyhead[RO]{\rightbotmark}

Code:

\documentclass[twoside]{report}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{blindtext}
\usepackage{etoolbox}


%http://tex.stackexchange.com/a/13395/56480
\let\Oldpart\part
\newcommand{\parttitle}{}
\renewcommand{\part}[1]{
    \Oldpart{#1}
    \renewcommand{\parttitle}{#1}   
}

\makeatletter
\newcommand*{\rightbotmark}{%
    \expandafter\@rightmark\botmark\@empty\@empty
}
\makeatother

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\chaptermark}[1]{\markboth{\parttitle: #1}{}}
\renewcommand{\sectionmark}[1]{\markright{#1}}

\fancyhead[RO]{\rightbotmark}
\fancyhead[LE]{\leftmark}
\fancyfoot[C]{\thepage}

%http://tex.stackexchange.com/a/19741/56480
\patchcmd{\chapter}{plain}{fancy}{}{}

\begin{document}

\tableofcontents
\part{First Part}
\chapter{First Chapter}
\blindtext[1]
\section{First Section}
\blindtext[5]
\section{Second Section}
\blindtext[7]
\chapter{Second Chapter}
\blindtext[1]
\section{Third Section}
\blindtext[2]
\chapter{Third Chapter}
\blindtext[1]
\section{Fourth Section}
\blindtext[5]
\end{document}

Answer 2

Here is a solution with titlesec and etoolbox. We have to redefine \part from within titlesec:

\documentclass[twoside]{report}
\usepackage[english]{babel}
\usepackage{blindtext}
\usepackage{etoolbox}

\usepackage[pagestyles,  outermarks,  clearempty]{titlesec}%
\titleformat{\part}[display]{\filcenter\bfseries\Huge}{\partname~\thepart}{3ex}{}[\thispagestyle{empty}]
\newpagestyle{mypagestyle}{
\settitlemarks{part, chapter, section}
\headrule
\sethead[\parttitle:   \chaptertitle][][]{}{}{\sectiontitle}
\setfoot{}{\thepage}{}
}
\pagestyle{mypagestyle}
\patchcmd{\chapter}{plain}{mypagestyle}{}

\begin{document}

\tableofcontents\thispagestyle{plain}
\part{First Part}
\chapter{First Chapter}%\thispagestyle{mypagestyle}
\blindtext[1]
\section{First Section}
\blindtext[5]
\section{Second Section}
\blindtext[7]
\chapter{Second Chapter}
\blindtext[1]
\section{Third Section}
\blindtext[2]
\chapter{Third Chapter}
\blindtext[1]
\section{Fourth Section}
\blindtext[5]

\end{document}