Enumerative combinatorics is an area of mathematics that is both highly accessible for students and widely applicable to other sciences and areas of mathematics (Kapur, 1970; Lockwood, Wasserman, & Tillema, 2020). One important class of problems in combinatorics is combinatorial proofs of binomial identities, which is a type of proof that argues for the veracity of an identity by arguing that each side enumerates a (finite) set of outcomes. The validity of a combinatorial proof lies in the fact that a set can have only one cardinality. Such proofs suggest an analytical proof scheme (Harel and Sowder, 1998) and have been considered to be examples of proofs that explain (in the sense of Hersh, 1993) with respect to an enumerative representation system (Lockwood, Caughman, & Weber, 2020). Combinatorial proofs also differ from other types of proofs students may encounter in several important ways. One feature of combinatorial proofs is that they are comprised exclusively of sentences and paragraphs; that is, a student producing a combinatorial proof must combinatorially interpret symbols appearing in the identity without algebraically manipulating those symbols. This feature has potential implications for students, since researchers have found that combinatorial reasoning can be a notoriously difficult for students (e.g., Batanero et al., 1997, and Lockwood, 2014b) and that some students are less likely to accept an argument to be a rigorous mathematical proof if it does not contain symbolic manipulations (e.g., Martin & Harel, 1989). In addition, while there are a couple of prior studies that have looked at students’ combinatorial proof activity (Engelke & CadwalladerOlsker, 2010; Lockwood, Reed, & Erickson, in press), much remains unknown regarding what students and mathematicians attend to as they produce combinatorial proofs. For instance, it has also never been verified with empirical evidence whether or not students or mathematicians do indeed consider combinatorial proofs to be proofs that explain, and even less is known regarding whether these populations consider combinatorial proofs to be proofs that convince.
In my dissertation study, I seek to answer the following research questions:
1. To what extent do experienced provers (including students and mathematicians) believe that combinatorial proofs of binomial identities are convincing and/or explanatory, and why?
2. What proof schemes do undergraduate students who are experienced provers use to discuss and characterize combinatorial proof?
3. What do the answers to these questions say about the nature of combinatorial proof (including how it may differ from other types of proof)?
4. What are some other insights about combinatorial proof that can be gained from interviewing experienced provers?
To answer these questions, I conducted clinical interviews with five upper-division mathematics students and eight mathematicians to investigate what they attended to as they produced and evaluated combinatorial proofs and how they viewed combinatorial proof as different from other types of proof. This dissertation begins with overall summaries of relevant literature, theory, and the methods involved in the overall study. Then, the results of the dissertation are presented in three manuscripts, where I describe the students’ and mathematicians’ perceptions of combinatorial proof using two theoretical frameworks: proofs that explain and/or convince (Hersh, 1993) and proof schemes (Harel & Sowder, 1998). I also use Lockwood’s (2013) model and the construct of cognitive models to describe an important aspect of students’ and mathematicians’ combinatorial reasoning that had implications for their success producing combinatorial proofs: cognitive models of multiplication.
In the first manuscript chapter of my dissertation, I describe the results of my investigation into whether students and mathematicians viewed combinatorial proof as explanatory or convincing (Hersh, 1993), and why. I found that all 14 participants felt that combinatorial proofs are equally or more explanatory than other types of proofs, but participants demonstrated a variety of perspectives regarding the extent to which combinatorial proofs are convincing. These findings provide empirical evidence for Lockwood et al.’s (2020) claim that combinatorial proofs are usually proofs that explain within the enumerative representation system, as well as provide insights on the nature of combinatorial proof as a mathematics topic.
In the second manuscript chapter of my dissertation, I discuss the proof schemes (Harel & Sowder, 1998) that students used to discuss and characterize combinatorial proof compared with other types of proof. I found that students used authoritarian, ritual, perceptual empirical, transformational analytical, and contextual restrictive proof schemes, and that these proof schemes had implications for the students’ perspectives regarding whether (and why) combinatorial proof constitutes rigorous mathematical proof. I also discuss whether and how other proof schemes may emerge for students engaging in combinatorial proof.
Finally, in my third manuscript chapter, I focus on a specific phenomenon that emerged during my interviews with mathematicians and students as they engaged in combinatorial proof production. In particular, participants used a wide variety of cognitive models to interpret multiplication by a constant when reasoning about binomial identities, some of which seemed to be more (or less) effective in helping produce a combinatorial proof. I present these cognitive models and describe episodes that illustrate implications of these cognitive models for my participants’ work on proving binomial identities. My findings both inform research on combinatorial proof and highlight the importance of understanding subtleties of the familiar operation of multiplication.
Overall, in addition to the specific results and findings presented in each of the papers, these three manuscripts supported four main takeaways regarding students’ and mathematicians’ reasoning about and engagement with combinatorial proof: 1) students can successfully produce combinatorial proofs and recognize their activity constitutes proof; 2) combinatorial proof may be viewed by some students as intuitive arguments but not formal proofs; 3) the contexts used in combinatorial proofs are important; and 4) difficulties in solving counting problems can carry over to difficulties in combinatorial proof production. These findings have implications for practitioners and researchers. For a start, both teachers and researchers should be aware that students may have a variety of conceptions about combinatorially proof as they teach and conduct proof-education research, respectively. In the classroom, instructors should understand that some students may believe combinatorial proof is less valid than algebraic, induction, or other types of proof for a variety of reasons, and so instructors should clarify for students why correct combinatorial proofs are indeed mathematically rigorous and logically valid. Instructors should also have discussions with their students about the element selection cognitive model of multiplication and highlight its relationship with the Multiplication Principle. Lastly, when researchers draw conclusions about student thinking about proof, they should be mindful that some of these conclusions may apply differently to student thinking about combinatorial proof.